Pseudo-code:

text
max_rooms = 0
for i from 0 to n-1:
    current_overlaps = 0
    for j from 0 to n-1:
        if intervals[i] and intervals[j] overlap:
            current_overlaps += 1
    max_rooms = max(max_rooms, current_overlaps)
return max_rooms

Why it fails: The time complexity of this approach is $O(N^2)$. With $N$ up to $10^4$, this results in approximately $10^8$ operations, which is inefficient and may lead to a Time Limit Exceeded (TLE) error. Furthermore, checking pairwise overlaps does not strictly guarantee finding the peak concurrency correctly without careful implementation regarding the specific time points.

Core Insight for Meeting Rooms II

The key intuition for the optimal LeetCode 253 solution is to process meetings in chronological order of their start times. By doing so, we simulate the flow of time. When a new meeting starts, we only care about one thing: has any previous meeting finished?

If a previous meeting has finished, we can reuse that room. If multiple meetings have finished, we ideally want to reuse the room that became free earliest (or any free room, but tracking the earliest end time is sufficient). If no meetings have finished, we must allocate a new room.

The Min-Heap serves as a container for "active meetings," specifically storing their end times.

1. The invariant enforced by the Min-Heap is that the root always holds the smallest end time among all currently active meetings.
2. When we encounter a new meeting, we compare its start_time with the min_end_time (heap root).
3. If start_time >= min_end_time, the meeting at the root has ended. We can remove it from the heap (freeing the room) and add the new meeting's end time (reusing the room).
4. If start_time < min_end_time, the earliest ending meeting is still ongoing. Therefore, all other active meetings are also ongoing. We must allocate a new room (push the new end time to the heap).

Visual Description: Imagine a timeline moving from left to right. The heap represents the set of rooms currently occupied. The value in the heap represents the time the room becomes free. As we iterate through sorted meetings, we check the "soonest to be free" room. If the current meeting starts after that time, we update that room's finish time. If not, we add a new room to our set. The size of this set grows only when necessary and never shrinks below the required capacity.

Execution Flow

Let's trace the algorithm with intervals = [[0, 30], [5, 10], [15, 20]].

1. Sort: Intervals are already sorted by start time: [0, 30], [5, 10], [15, 20].
2. Initialize: Min-Heap [].
3. Step 1 (First Meeting):
   • Current: [0, 30].
   • Action: Push 30.
   • Heap: [30].
4. Step 2:
   • Current: [5, 10].
   • Check: Is 5 >= 30? No. No room is free.
   • Action: Push 10.
   • Heap: [10, 30] (Sorted order).
5. Step 3:
   • Current: [15, 20].
   • Check: Is 15 >= 10 (Heap min)? Yes. The meeting ending at 10 is over.
   • Action: Pop 10. Push 20.
   • Heap: [20, 30].
6. End:
   • Heap size is 2.
   • Result: 2 rooms required.

Proof of Correctness

The correctness relies on the Greedy Choice Property. By sorting intervals by start time, we ensure that when we consider a meeting M, all meetings that started before M have already been processed.

To minimize rooms, we must maximize reuse. A room is reusable for meeting M if and only if the previous meeting in that room finished by M.start. The Min-Heap provides the earliest finishing time E_min of all currently occupied rooms.

1. If M.start >= E_min, the room associated with E_min is free. Using this room is optimal because it prevents allocating a new resource unnecessarily.
2. If M.start < E_min, then M overlaps with the meeting ending at E_min. Since E_min is the earliest end time, M also overlaps with every other active meeting in the heap (as their end times are $\ge E_{min}$). Therefore, no existing room is free, and a new room must be allocated.

Thus, the heap size exactly tracks the accumulation of necessary rooms.

Reference Implementation

C++ Solution for LeetCode 253

cpp
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        // Sort by start time
        sort(intervals.begin(), intervals.end());

        // Min-heap to store end times of active meetings
        // priority_queue is a max-heap by default, use greater for min-heap
        priority_queue<int, vector<int>, greater<int>> minHeap;

        // Add the first meeting's end time
        minHeap.push(intervals[0][1]);

        for (size_t i = 1; i < intervals.size(); ++i) {
            // If the room with the earliest end time is free, reuse it (pop)
            if (intervals[i][0] >= minHeap.top()) {
                minHeap.pop();
            }
            // Add the current meeting's end time (either to a new room or the reused one)
            minHeap.push(intervals[i][1]);
        }

        return minHeap.size();
    }
};

Java Solution for LeetCode 253

java
import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        // Sort by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // Min-Heap to track end times
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add the first meeting's end time
        minHeap.add(intervals[0][1]);

        for (int i = 1; i < intervals.length; i++) {
            // Check if the earliest ending meeting has finished
            if (intervals[i][0] >= minHeap.peek()) {
                minHeap.poll(); // Reuse the room
            }
            
            // Add current meeting's end time to the heap
            minHeap.add(intervals[i][1]);
        }

        // The size of the heap is the minimum rooms required
        return minHeap.size();
    }
}

Python Solution for LeetCode 253

python
import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
            
        # Sort intervals by start time
        intervals.sort(key=lambda x: x[0])
        
        # Min-heap to store end times
        free_rooms = []
        
        # Push the first meeting's end time
        heapq.heappush(free_rooms, intervals[0][1])
        
        for i in range(1, len(intervals)):
            # If the new meeting starts after or when the earliest meeting ends
            if intervals[i][0] >= free_rooms[0]:
                heapq.heappop(free_rooms)
            
            # Push the current meeting's end time
            heapq.heappush(free_rooms, intervals[i][1])
            
        return len(free_rooms)