N Meetings in One Room
Given meeting start and end times and one room, pick the maximum number of non-overlapping meetings.
- 1 <= n <= 10⁵
- 0 <= start[i] < end[i] <= 10⁹
- One room; meetings may not overlap
Intuition
N meetings in one room gives start and end times and a single room, and asks for the maximum number of non-overlapping meetings you can hold. The instinct to prefer short meetings, or ones that start early, both fail — and understanding why points straight at the right rule. Shortest-first fails because a short meeting in the middle of the day can block two others on either side. Earliest-start fails because a meeting starting at 9am and running until 6pm blocks everything. What actually matters is when the room becomes free again. A meeting that ends earliest leaves the largest possible remainder of the day for everything after it: - Sort by end time and take every meeting that starts after the previously chosen one ends. The proof is an exchange argument, and it is short enough to be worth carrying. Take any optimal schedule and look at its first meeting. Swap it for the meeting that ends earliest overall. The replacement ends no later, so it cannot conflict with anything the original schedule kept, and the count is unchanged. Repeating this converts any optimum into the greedy solution without ever losing a meeting — so greedy achieves the maximum too.
The classic activity-selection greedy: to fit the most items into a timeline, always take the one that finishes soonest, because it leaves the most room for everything after it. The sort key is the whole solution. Whenever you're maximising a count of non-overlapping things, sort by end; whenever you're merging or covering, sort by start.
Approach
Before reading on: price up what sorting first costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n) time and O(n) space.
Sort meetings by finish time
Order by end time ascending. Neither duration nor start time is the right key — what determines how much of the day survives a choice is only when the room frees up.
Track the last chosen end time
Keep a variable holding when the room becomes free, initialised so that the first meeting always qualifies. This single value is the entire state the sweep needs.
Take every compatible meeting in order
Walk the sorted list; if a meeting's start is after lastEnd, take it, increment the count and update lastEnd. Otherwise skip it — it overlaps something already committed to.
Decide the boundary case deliberately
If a meeting starts at exactly the moment another ends, most versions of this problem allow both. Check whether the statement wants start > lastEnd or start >= lastEnd — this single comparison changes the answer on touching intervals and is the most common source of a wrong result.
Understand why greedy is optimal
Any optimal schedule's first meeting can be swapped for the earliest-ending one without conflict or loss, since the replacement frees the room no later. Repeating the swap turns an optimum into the greedy answer, proving greedy matches the maximum.
Cost of the sweep
Sorting is O(n log n) and the single pass is O(n), so sorting dominates. Space is O(n) if you sort index pairs to report which meetings were chosen, O(1) if only the count is needed.
Solution & live demo
Common pitfalls
Sorting by start time
meetings = sorted(zip(start, end))
meetings = sorted(zip(end, start))
Earliest-starting is not earliest-finishing: one long meeting that begins first can block several short ones. Sorting by end time is what makes the greedy choice provably optimal — it always frees the room at the earliest possible moment.
Sorting by duration
meetings.sort(key=lambda m: m[1] - m[0])
meetings = sorted(zip(end, start))
Intuitive but wrong: a short meeting sitting in the middle of the day can straddle and block two others, while a longer early one blocks nothing. What matters is when the room becomes free, not how long it was occupied.
Allowing a meeting to start exactly when the last ends
if s >= last_end:
if s > last_end:
Under GFG's convention one meeting must finish strictly before the next begins, so touching endpoints count as a clash. (LeetCode's interval problems often go the other way — check which convention the statement uses.)
Edge cases
Classic GFG version requires strict start > lastEnd; back-to-back with equal times is rejected.
Any order among ties works — each blocks the same suffix.