Meeting Rooms II (LeetCode 253)

The problem

You get a list of meetings [start, end]. Return the minimum number of conference rooms needed so that every meeting has a room. A room freed at time 10 can host a meeting starting at time 10.

Input:  [[0, 30], [5, 10], [15, 20]]
Output: 2

[0, 30] needs a room the whole time. [5, 10] needs a second room, and [15, 20] can reuse that second room once [5, 10] has ended.

How to think about it

Start with brute force. For every moment in time, count how many meetings are running, and take the maximum. Checking each meeting’s start against every other meeting is O(n²).

Reframe: rooms needed = peak number of meetings running at once. You never need more rooms than the largest overlap, and you always need at least that many. So the real question is “what is the maximum overlap?”

The key insight: you only care about events, not which meeting they belong to. A start means “one more room busy”. An end means “one room free”. Sort all start times and all end times separately. Walk the starts in order; before placing each one, release every room whose end time is at or before this start. Then claim a room. The highest count you reach is the answer.

Which pattern is this? Intervals with a sweep line. The tell is “maximum simultaneous overlaps” or “minimum resources”. The classic alternative is a min-heap of end times (see the heaps lesson), which does the same release-then-claim step.

Approach

1. Make starts = sorted start times and ends = sorted end times.
2. Set rooms = 0, best = 0, and an end pointer e = 0.
3. For each start s in order: while ends[e] <= s, a meeting has finished, so e += 1 and rooms -= 1.
4. Then rooms += 1 for the meeting starting now, and update best.
5. Return best.

Solution

def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = 0; best = 0; e = 0
    for s in starts:
        while ends[e] <= s:            # free every room that has ended by time s
            e += 1; rooms -= 1
        rooms += 1; best = max(best, rooms)   # this meeting takes a room
    return best
# min_meeting_rooms([[0,30],[5,10],[15,20]]) -> 2

Dry run

starts = [0, 5, 15], ends = [10, 20, 30].

The answer is 2.

Complexity

• Time: O(n log n). Two sorts; the sweep is O(n) because e only moves forward.
• Space: O(n). The two sorted lists.

Edge cases and pitfalls

• Empty list returns 0; the loop never runs.
• Back-to-back meetings ([[1, 5], [5, 10]]) need 1 room. Use <= when freeing, so a room that ends at 5 is free for a meeting at 5.
• Zero-length meetings. The code relies on start < end, which LeetCode guarantees. With [[5, 5]] the while loop would free a room that was never claimed and then index past the end of ends, raising IndexError.
• Sorting the pairs together and checking only neighbours undercounts: the room count depends on all meetings still running, not just the previous one.
• Heap alternative: sort meetings by start and keep a min-heap of end times; pop when the earliest end is at most the new start. Same complexity, and it is the version many interviewers expect.

Related problems

• Meeting Rooms (LeetCode 252): the yes/no version: is one room enough?
• Car Pooling (LeetCode 1094): the same sweep, with weighted events and a capacity check.
• Task Scheduler (LeetCode 621): another scheduling problem from the heaps lesson.