Loading problems...
TL;DR: Sort the meetings by start time and use a Min-Heap to track the end times of ongoing meetings; the size of the heap represents the minimum number of conference rooms required.
The Meeting Rooms II problem asks us to determine the minimum resources needed to accommodate a schedule of events. Given an array of time intervals consisting of start and end times, we must calculate the peak number of overlapping intervals. If two meetings overlap, they require separate rooms. If a meeting ends before or exactly when another begins, the room can be reused.
This is a classic resource allocation problem frequently seen in technical interviews at top tech companies. The LeetCode 253 solution requires efficient handling of time-based constraints to optimize resource usage.
The naive approach involves comparing every meeting with every other meeting to determine the maximum number of overlaps at any point in time. Alternatively, one could discretize time (if the range is small) and increment a counter for every time unit a meeting is active.
Naive Algorithm:
max_overlaps to 0.max_overlaps with the maximum count found.Pseudo-code:
textmax_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 . With up to , this results in approximately 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.
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.
start_time with the min_end_time (heap root).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).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.

Let's trace the algorithm with intervals = [[0, 30], [5, 10], [15, 20]].
[0, 30], [5, 10], [15, 20].[].[0, 30].30.[30].[5, 10].5 >= 30? No. No room is free.10.[10, 30] (Sorted order).[15, 20].15 >= 10 (Heap min)? Yes. The meeting ending at 10 is over.10. Push 20.[20, 30].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.
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.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 ). Therefore, no existing room is free, and a new room must be allocated.Thus, the heap size exactly tracks the accumulation of necessary rooms.
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(); } };
javaimport 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(); } }
pythonimport 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)
Time Complexity:
Space Complexity:
The Heap (Scheduling / Minimum Cost) pattern is versatile. Here is how it applies to similar problems:
K quality workers while iterating through workers sorted by wage-to-quality ratio.Why did I get a Time Limit Exceeded (TLE)?
Why is my output incorrect for edge cases?
Why does my code fail on contiguous meetings (e.g., [0,5], [5,10])?
>) instead of greater-than-or-equal (>=) when comparing start time to heap top.Why is the logic failing even with a Heap?
intervals array by start time before processing.