What pattern does Meeting Rooms II use?

The Pattern: Heap / Priority Queue (Interval Scheduling Resource Allocation) The Heuristic: Use a min-heap to track the earliest finishing meeting to efficiently free rooms; the heap size at any time reflects the number of concurrent meetings, which equals the minimum rooms needed.

Meeting Rooms II - LeetCode Solution & Explanation

Q: How do you solve Meeting Rooms II?

Sort intervals by start time. Iterate through each meeting, and while the min-heap is not empty and the current meeting's start time is greater than or equal to the earliest end time in the heap, pop from the heap to free a room. Push the current meeting's end time onto the heap. Track the maximum heap size during iteration, which represents the minimum rooms required.

Q: What is the time complexity of Meeting Rooms II?

O(n log n). Sorting the intervals takes O(n log n). Each interval is pushed and popped at most once from the min-heap, each operation costing O(log n), resulting in O(n log n) overall.

Problem

Given an array of meeting time intervals consisting of start and end times, return the minimum number of conference rooms required to hold all the meetings without overlaps.

1 ≤ intervals.length ≤ 10⁴
0 ≤ start_i < end_i ≤ 10⁶

Example

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

Output: 2

The algorithm first sorts the intervals by start time: [[0,30],[5,10],[15,20]]. It initializes a min-heap to track end times of ongoing meetings. The first meeting [0,30] is added to the heap. The second meeting [5,10] starts before the earliest ending meeting (30), so it requires a new room; its end time 10 is pushed onto the heap. The third meeting [15,20] starts after the earliest ending meeting (10), so the room that ended at 10 is freed (popped from the heap), and the new meeting's end time 20 is pushed. The heap size never exceeds 2, so 2 rooms are needed.

Approach

Straightforward Solution

A brute-force approach checks every pair of intervals for overlap, counting maximum overlaps, resulting in O(n^2) time complexity, which is too slow for large inputs.

Core Observation

The minimum number of rooms required equals the maximum number of overlapping meetings at any point in time. Sorting intervals by start time allows sequential processing, and a min-heap efficiently tracks the earliest finishing meeting to free rooms.

Path to Optimal

Sorting intervals by start time orders meetings chronologically. Using a min-heap to track end times of ongoing meetings allows efficient detection of room availability: if the current meeting starts after or at the earliest end time, that room can be reused (pop from heap). Otherwise, a new room is needed (push end time). This approach reduces complexity to O(n log n) due to sorting and heap operations.

Optimal Approach

Sort intervals by start time. Iterate through each meeting, and while the min-heap is not empty and the current meeting's start time is greater than or equal to the earliest end time in the heap, pop from the heap to free a room. Push the current meeting's end time onto the heap. Track the maximum heap size during iteration, which represents the minimum rooms required.

Time

O(n log n)

Sorting the intervals takes O(n log n). Each interval is pushed and popped at most once from the min-heap, each operation costing O(log n), resulting in O(n log n) overall.

Space

O(n)

The min-heap can hold up to n end times in the worst case (all meetings overlap), so auxiliary space is O(n). This space is necessary to track ongoing meetings.

Solution

1import heapq
2
3class Solution:
  def minMeetingRooms(self, intervals: list[list[int]]) -> int:
      intervals.sort(key=lambda i: i[0])
      
      min_heap = []
      max_rooms = 0
      
      for start, end in intervals:
          while min_heap and start >= min_heap[0]:
              heapq.heappop(min_heap)
          
          heapq.heappush(min_heap, end)
          max_rooms = max(max_rooms, len(min_heap))
      
      return max_rooms

Step-by-Step Solution

1

Sort Meetings by Start Time to Process Chronologically

5	`intervals.sort(key=lambda i: i[0])`

Objective

To order the meetings so that they can be processed in chronological order of their start times.

Key Insight

Sorting intervals by start time is essential because it allows the algorithm to consider meetings in the order they begin, which is necessary to detect overlaps and manage room allocation efficiently. Without sorting, the algorithm cannot reliably track which rooms become free when.

Interview Quick-Check

Core Logic

Sorting by start time ensures that meetings are processed in the order they occur, enabling correct overlap detection.

Common Pitfalls & Bugs

Failing to sort intervals leads to incorrect room allocation because meetings may be processed out of chronological order.

2

Use Min-Heap to Track Earliest Meeting End Times and Free Rooms

7min_heap = []
10for start, end in intervals:
11    while min_heap and start >= min_heap[0]:
12        heapq.heappop(min_heap)
14    heapq.heappush(min_heap, end)

Objective

To maintain the end times of ongoing meetings and efficiently determine when rooms become available.

Key Insight

A min-heap keeps track of the earliest finishing meeting at the top, allowing the algorithm to quickly check if the current meeting can reuse a room. If the current meeting starts after or at the earliest end time, that room is freed (pop from heap). Otherwise, a new room is allocated (push end time). This dynamic management of room availability is the core of the solution.

Interview Quick-Check

Core Logic

The min-heap stores end times of meetings currently occupying rooms; popping from it frees rooms when meetings end before the next starts.

State & Boundaries

The while loop condition ensures all rooms that have become free before the current meeting starts are released.

Common Pitfalls & Bugs

Not popping all ended meetings before pushing the current one can lead to overestimating the number of rooms needed.

Complexity

Heap operations maintain O(log n) time per insertion and removal, keeping the overall algorithm efficient.

3

Track Maximum Concurrent Meetings to Determine Minimum Rooms

8max_rooms = 0
15    max_rooms = max(max_rooms, len(min_heap))

Objective

To record the maximum number of rooms occupied simultaneously during the iteration.

Key Insight

The size of the min-heap after adding the current meeting's end time represents the number of rooms currently in use. Tracking the maximum heap size throughout the iteration captures the peak concurrency, which equals the minimum number of rooms required to schedule all meetings without overlap.

Interview Quick-Check

Core Logic

Updating max_rooms with the current heap size captures the peak number of concurrent meetings.

Common Pitfalls & Bugs

Failing to update the maximum after each insertion can cause incorrect results.

4

Return the Minimum Number of Rooms Required

17	`return max_rooms`

Objective

To output the final computed minimum number of rooms needed to schedule all meetings.

Key Insight

After processing all intervals, the maximum number of concurrent meetings recorded is the minimum number of rooms required. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Returning max_rooms provides the final answer representing the minimum rooms needed.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

while min_heap and start >= min_heap[0]:

While there are meetings that have ended before the current meeting starts, free those rooms.

Removing all meetings that ended before the current start time frees rooms for reuse, preventing unnecessary room allocation.

Line 12 Critical

heapq.heappop(min_heap)

Pop the earliest ending meeting from the min-heap to free a room.

Popping the earliest end time removes the meeting that has finished, making its room available for the current meeting.

Line 5 Core

intervals.sort(key=lambda i: i[0])

Sort the intervals by their start times in ascending order.

Sorting ensures meetings are processed chronologically, which is essential for correctly detecting overlaps and managing room allocation.

Line 7 Core

min_heap = []

Initialize an empty min-heap to track end times of ongoing meetings.

The min-heap allows efficient retrieval of the earliest finishing meeting, enabling quick room reuse decisions.

Line 14 Core

heapq.heappush(min_heap, end)

Add the current meeting's end time to the min-heap, allocating a room.

Pushing the current meeting's end time reserves a room until this meeting finishes, maintaining accurate room usage tracking.

Line 15 Core

max_rooms = max(max_rooms, len(min_heap))

Update the maximum number of rooms needed based on current concurrent meetings.

The heap size reflects the number of ongoing meetings; tracking its maximum captures the peak room requirement.

Line 10 Standard

for start, end in intervals:

Iterate over each meeting's start and end times in sorted order.

Processing meetings in order allows the algorithm to manage room allocation dynamically as meetings start and end.

Line 17 Standard

return max_rooms

Return the maximum number of rooms required to schedule all meetings.

This final return outputs the minimum number of rooms needed to avoid any meeting overlaps.

Line 8 Standard

max_rooms = 0

Initialize a variable to track the maximum number of rooms needed.

This variable records the peak number of concurrent meetings, which determines the minimum rooms required.

Test Your Understanding

Why does the size of the min-heap at any point represent the minimum number of rooms required?

Because the min-heap contains the end times of all meetings currently occupying rooms; its size equals the number of concurrent meetings, which directly corresponds to the number of rooms needed to avoid overlap.

Don't just read it. Drill it.

Reconstruct Meeting Rooms II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Meeting Rooms II drill

or drill a free problem

1	`import heapq`
2
3	`class Solution:`
4	`def minMeetingRooms(self, intervals: list[list[int]]) -> int:`
5	`intervals.sort(key=lambda i: i[0])`
6
7	`min_heap = []`
8	`max_rooms = 0`
9
10	`for start, end in intervals:`
11	`while min_heap and start >= min_heap[0]:`
12	`heapq.heappop(min_heap)`
13
14	`heapq.heappush(min_heap, end)`
15	`max_rooms = max(max_rooms, len(min_heap))`
16
17	`return max_rooms`

7	`min_heap = []`
10	`for start, end in intervals:`
11	`while min_heap and start >= min_heap[0]:`
12	`heapq.heappop(min_heap)`
14	`heapq.heappush(min_heap, end)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Sort Meetings by Start Time to Process Chronologically

Use Min-Heap to Track Earliest Meeting End Times and Free Rooms

Track Maximum Concurrent Meetings to Determine Minimum Rooms

Return the Minimum Number of Rooms Required

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.