LeetCode 253: Meeting Rooms II

Problem Restatement

We are given a list of meeting intervals.

Each interval is:

[start, end]

A meeting room can host only one meeting at a time.

We need to determine the minimum number of meeting rooms required so that all meetings can happen without overlap.

Input and Output

Example function shape:

def minMeetingRooms(intervals: list[list[int]]) -> int:
    ...

Examples

Example 1:

intervals = [[0, 30], [5, 10], [15, 20]]

Timeline:

• Meeting [0, 30] uses one room.
• Meeting [5, 10] overlaps with [0, 30], so we need a second room.
• Meeting [15, 20] starts after [5, 10] ends, so that second room can be reused.

Answer:

2

Example 2:

intervals = [[7, 10], [2, 4]]

These meetings do not overlap.

Only one room is needed.

Answer:

1

Example 3:

intervals = [[1, 5], [2, 6], [3, 7]]

All meetings overlap.

At one moment, three meetings are active simultaneously.

Answer:

3

First Thought: Track Every Room Manually

One approach is to maintain a list of rooms.

For every new meeting:

1. Try to place it into an existing room.
2. If no room is available, create a new room.

This works, but checking all rooms repeatedly can become expensive.

Problem With Naive Simulation

Suppose we already have many rooms.

To place a new meeting, we may need to scan every room to find one that becomes free early enough.

That gives:

in the worst case.

We need a faster way to know which room becomes available first.

Key Insight

At any moment, the most important room is the one whose meeting ends earliest.

Why?

If the earliest-ending room is still busy, then every other room is also busy.

If the earliest-ending room becomes free, we can reuse it immediately.

So we should efficiently track:

Which active meeting ends first?

A min heap is perfect for this.

The heap stores meeting end times.

The smallest end time always stays at the top.

Understanding the Heap

Suppose meetings are sorted by start time:

[[0, 30], [5, 10], [15, 20]]

We process them one by one.

Step 1

Meeting:

[0, 30]

No rooms exist yet.

Create one room.

Heap:

[30]

The room becomes free at time 30.

Step 2

Meeting:

[5, 10]

The earliest room becomes free at 30.

Since:

the room is still occupied.

We need another room.

Heap:

[10, 30]

Now two rooms are active.

Step 3

Meeting:

[15, 20]

The earliest room becomes free at 10.

Since:

15 >= 10

that room is available again.

We remove 10 from the heap and reuse that room.

Heap becomes:

[20, 30]

Still only two rooms are needed.

Algorithm

1. Sort meetings by start time.
2. Create a min heap.
3. Push the first meeting’s end time into the heap.
4. For each remaining meeting:
   • Look at the smallest end time in the heap.
   • If the current meeting starts after or exactly when that meeting ends:
     • Reuse the room by removing the smallest end time.
   • Push the current meeting’s end time into the heap.
5. The heap size equals the number of rooms currently in use.
6. The maximum heap size needed during processing is the answer.

In this implementation, the heap size after processing all meetings already equals the minimum required number of rooms.

Correctness

The heap always stores the end times of meetings currently occupying rooms.

The smallest heap value represents the room that becomes free first.

When processing a meeting:

[start, end]

there are two possibilities.

If:

then the earliest room is already free, so reusing that room is valid.

Removing the smallest end time from the heap correctly frees that room.

Otherwise:

then even the earliest-ending room is still occupied. Therefore every existing room is occupied, and a new room is required.

Because meetings are processed in chronological order, this greedy choice is always optimal. Reusing the earliest available room preserves the maximum number of future scheduling options.

Therefore the algorithm computes the minimum number of rooms required.

Complexity

Each heap insertion or removal costs:

Implementation

import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0

        intervals.sort()

        heap = []

        heapq.heappush(heap, intervals[0][1])

        for start, end in intervals[1:]:

            if start >= heap[0]:
                heapq.heappop(heap)

            heapq.heappush(heap, end)

        return len(heap)

Code Explanation

We first handle empty input:

if not intervals:
    return 0

Then we sort meetings by start time:

intervals.sort()

The heap stores active meeting end times.

heap = []

We insert the first meeting’s end time:

heapq.heappush(heap, intervals[0][1])

Now we process remaining meetings.

for start, end in intervals[1:]:

The earliest room to become free is:

heap[0]

If the current meeting starts after that room becomes free:

if start >= heap[0]:

we reuse the room:

heapq.heappop(heap)

Then we store the new ending time:

heapq.heappush(heap, end)

The heap size represents the number of rooms currently occupied.

After all meetings are processed, the heap size equals the minimum number of rooms required.

Testing

def run_tests():
    s = Solution()

    assert s.minMeetingRooms([[0, 30], [5, 10], [15, 20]]) == 2
    assert s.minMeetingRooms([[7, 10], [2, 4]]) == 1
    assert s.minMeetingRooms([[1, 5], [2, 6], [3, 7]]) == 3
    assert s.minMeetingRooms([]) == 0
    assert s.minMeetingRooms([[1, 10]]) == 1
    assert s.minMeetingRooms([[1, 5], [5, 10]]) == 1
    assert s.minMeetingRooms([[1, 4], [2, 3], [3, 6]]) == 2
    assert s.minMeetingRooms([[13, 15], [1, 13]]) == 1

    print("all tests passed")

run_tests()

Test meaning: