N Meetings in One Room
Given meeting start and end times and one room, pick the maximum number of non-overlapping meetings.
Intuition
The meeting that ends earliest leaves the most room for everything after it — choosing it can never hurt. Sort by end time and greedily take every meeting that starts after the last chosen one ends.
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
Sort by end time
Finishing early is the only thing that matters for what fits afterward — not duration, not start time.
Sweep and take
Keep lastEnd. For each meeting in order, if start > lastEnd, take it and update lastEnd.
Why greedy is optimal
Exchange argument: any optimal schedule can swap its first meeting for the earliest-ending one without losing meetings — so the greedy prefix is always extendable to an optimum.
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.