Meeting rooms II
StopHeap
- CH1 heap
27/27
Sort by start, and keep the end times of meetings in progress on a heap. Its biggest size is the rooms you need.
Step through it →Intervals
Sort intervals by start, then sweep once: each one can only overlap the last interval kept, so one comparison decides whether to merge.
Merge intervals: combine the ones that overlap
StopIntervals
intervals
Sort by start. Now an interval can only overlap the last one merged, never an earlier one.
Typical cost O(n log n) time (dominated by the sort), O(n) spaceFull lesson: Merge Intervals →
When to reach for it
- The input is ranges: meetings, bookings, time windows.
- You merge them, insert one, or count how many overlap.
- Sorted by start, each range only needs comparing with the last one kept.
- You're scheduling with the fewest rooms or machines.
What stays true
Sorted by start, a new interval either reaches the last merged one and stretches it, or starts past its end and begins a new one. So the last one is the only one it could overlap.
Merged intervals never touch
StopIntervals
InvariantThe merged intervals stay in order, with a gap between each.✓ Holds
Sort by start. Now an interval can only overlap the last one merged, never an earlier one.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
They share the point 4. Comparing with < instead of ≤ would keep them apart.
Merge intervals on the inputs that trip it up
StopIntervals
Sort by start. Now an interval can only overlap the last one merged, never an earlier one.
Answer[[1, 5]]Steps8
Variants
The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Merge intervals: combine the ones that overlap
StopIntervals
Sort by start. Now an interval can only overlap the last one merged, never an earlier one.
merge_intervals.py
def merge(intervals): intervals = sorted(intervals, key=lambda iv: iv[0]) merged = [] for start, end in intervals: if merged and start <= merged[-1][1]: merged[-1][1] = max(merged[-1][1], end) else: merged.append([start, end]) return mergedDrill it
Merge IntervalsRuns live,MediumMeeting Rooms IIRuns live,MediumInsert IntervalMedium
Non-overlapping IntervalsMedium