Meeting rooms & the sweep line
In one line
To find how many intervals are active at once, turn each interval into a +1 start event and a -1 end event, sort the events, and sweep while keeping a running count; the peak is the answer.
What it is
Meeting Rooms I asks whether one person can attend all meetings, which is true if no two overlap: sort by start and check each meeting starts at or after the previous one ends.
Meeting Rooms II asks for the minimum number of rooms needed, which equals the maximum number of meetings happening at the same moment.
The sweep line technique solves it: imagine a vertical line moving left to right across time. Each start adds one active meeting, each end removes one, and you track the highest count. A min-heap of end times is an equivalent approach.
Why interviewers ask
Meeting Rooms II is a very common interview problem, and the sweep line idea reaches far beyond it: peak concurrent users, maximum overlapping bookings, car pooling capacity, skyline outlines. Interviewers want the O(n log n) solution and correct handling of a meeting ending exactly when another starts.
How it works
- 1For each meeting [start, end), create two events: (start, +1) and (end, -1).
- 2Sort events by time. When times are equal, process ends before starts, so a room freed at 10 can host a meeting starting at 10. Sorting tuples (time, delta) does this automatically because -1 < +1.
- 3Sweep through the events, adding each delta to a running count of rooms in use.
- 4The maximum value the count reaches is the minimum number of rooms.
- 5Heap version: sort meetings by start; keep a min-heap of end times of rooms in use; if the earliest end is <= the new start, reuse that room (pop), then push the new end. The heap size at the end is the answer.
- 6Both versions are O(n log n) time and O(n) space.
Worked example · Meetings [[0, 30], [5, 10], [15, 20]]
- Events: (0, +1), (30, -1), (5, +1), (10, -1), (15, +1), (20, -1).
- Sorted: (0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1).
- t = 0: rooms 1, best 1. t = 5: rooms 2, best 2.
- t = 10: rooms 1. t = 15: rooms 2, best stays 2.
- t = 20: rooms 1. t = 30: rooms 0.
- Answer: 2 rooms. The long meeting [0, 30] keeps one room busy while the other two meetings share the second room.
Picture it
A turnstile counter at a building: every time someone enters you click up, every time someone leaves you click down. The highest number the counter ever showed is how many seats the building needed.
Reference code
def min_meeting_rooms(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # a meeting starts: +1 room
events.append((end, -1)) # a meeting ends: -1 room
# tuples sort by time, then delta: at equal times -1 comes first,
# so a room freed at 10 can be reused by a meeting starting at 10
events.sort()
rooms = best = 0
for _, delta in events:
rooms += delta
best = max(best, rooms)
return best
print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]])) # 2Each meeting adds one +1 and one -1 event. Sorting tuples orders by time, and at equal times -1 sorts before +1, which treats meetings as half-open: one ending at 10 frees its room for one starting at 10. The running count's peak is the minimum number of rooms.
Key patterns
Can attend all
When: Is there any overlap at all
How: Sort by start; fail if any meeting starts before the previous one ends. O(n log n).
Event sweep (+1 / -1)
When: Peak number of overlapping intervals
How: Make start and end events, sort with ends first on ties, track the running maximum.
Min-heap of end times
When: You also need to assign rooms
How: Sort by start; reuse the room that frees earliest if free, else open a new one.
Difference array
When: Times are small integers (for example minutes in a day)
How: diff[start] += 1, diff[end] -= 1, then a prefix sum gives the count at each time. O(n + T).
Two sorted arrays
When: You want a simple pointer version
How: Sort starts and ends separately; walk starts, and whenever a start >= the current end, move the end pointer and reuse a room.
Real-world use
Room and resource booking
Workplace tools like Microsoft Outlook room finders and Google Calendar room booking need to know how many rooms of a type are booked at each time slot to show availability.
Capacity planning for servers
From request logs with start and end times, a sweep gives peak concurrent connections, which decides how many server instances or database connections to provision.
Ride sharing and car pooling
Checking whether a vehicle with a fixed number of seats can serve a set of trips (pickup and drop-off points) is the same +passengers / -passengers sweep.
Telecom and license servers
Call centers and floating software licenses measure peak simultaneous calls or users, sweeping over session start and end times to size trunks or license counts.
In a project
A coworking space has 40 booking requests for tomorrow and wants to know the fewest meeting rooms it must open, and which room each booking gets.
- Sort bookings by start time.
- Keep a min-heap of (end_time, room_id) for rooms in use. For each booking, if the earliest-ending room is free by its start, pop it and reuse that room; otherwise open a new room id.
- Push (booking end, room id) and record the assignment.
- The number of room ids created is the minimum, and the assignments are the schedule.
Impact: The space opens exactly the number of rooms needed (the peak overlap), saving cleaning and heating for unused rooms, and every member gets a room assignment the night before.
Trade-offs
Use it when
- You need the maximum overlap, peak load or minimum resources
- Intervals are given in a batch
- You need counts at every moment (sweep) or assignments (heap)
Avoid it when
- Times are small bounded integers: a difference array is O(n + T) and simpler
- Intervals arrive and leave dynamically with queries in between: use a segment tree or ordered map of counts
Cost: O(n log n) time for sorting events or using the heap; O(n) space.
Common mistakes
- Processing starts before ends at equal times, which reports one room too many when a meeting ends exactly as another starts.
- Answering with the number of overlapping pairs instead of the peak concurrent count.
- In the heap version, comparing the new start with the latest end instead of the earliest end (the heap top).
- Sorting by end time instead of start time for the heap version.
- Not stating the half-open assumption to the interviewer.
Interview questions
Quick revision
- Min rooms = maximum number of overlapping meetings.
- Events: (start, +1), (end, -1); sort; track running max.
- Ties: ends before starts (tuple sort does this).
- Heap: sort by start; if heap top <= start, pop; push end; answer = heap size.
- Small integer times: difference array + prefix sum.
- Can-attend-all: sort by start, check neighbours.
- O(n log n) time, O(n) space.
Check yourself
1. Meetings [[1, 5], [5, 10]] (a meeting can start when another ends). How many rooms?
2. Meetings [[1, 4], [2, 5], [3, 6]]. How many rooms?
3. In the heap solution, what does the heap store?
4. What does the sweep line track as it moves across time?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.