Approach Summary
Sort by start. Min-heap of end times: if next meeting starts after earliest end, reuse that room (pop & push new end), else add a room.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Two Pointers with Separate Sorted Start and End Arrays | O(n log n) | O(n) | Sort starts and ends separately; advance end pointer when start >= end, otherwise allocate room. |
| 2 Approach 2: Min-Heap Tracking End Times (Optimal) | O(n log n) | O(n) | Maintain a min-heap of active meeting end times, popping when a room can be reused. |
Step 1: Baseline
Approach 1: Two Pointers with Separate Sorted Start and End Arrays
Time: O(n log n)
Space: O(n)
Collect all start times and sort them. Collect all end times and sort them. Walk through start times with index i: if starts[i] < ends[endIdx], an existing room is occupied, so allocate a new room. Otherwise, a room just became available, so advance endIdx without increasing room count.
Approach 1: Two Pointers with Separate Sorted Start and End Arrays Implementation
Approach 1: Two Pointers with Separate Sorted Start and End Arrays
public class Solution {
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0, endIdx = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[endIdx]) rooms++;
else endIdx++;
}
return rooms;
}
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int rooms = 0, endIdx = 0;
for (int i = 0; i < n; i++) {
if (starts[i] < ends[endIdx]) rooms++;
else endIdx++;
}
return rooms;
}
};class Solution:
def minMeetingRooms(self, intervals: list[list[int]]) -> int:
starts = sorted(i[0] for i in intervals)
ends = sorted(i[1] for i in intervals)
rooms, end_ptr = 0, 0
for start in starts:
if start < ends[end_ptr]:
rooms += 1
else:
end_ptr += 1
return roomsfunction minMeetingRooms(intervals) {
const starts = intervals.map(x => x[0]).sort((a, b) => a - b);
const ends = intervals.map(x => x[1]).sort((a, b) => a - b);
let rooms = 0, endPtr = 0;
for (let i = 0; i < starts.length; i++) {
if (starts[i] < ends[endPtr]) rooms++;
else endPtr++;
}
return rooms;
} Step 2: Most Optimized
Approach 2: Min-Heap Tracking End Times (Optimal)
Time: O(n log n)
Space: O(n)
Sort meetings by start time. Use a min-heap storing end times. For each meeting, if the top of the heap (earliest finishing meeting) finishes before current meeting starts, pop it (reusing that room). Then push current meeting end time. The heap size is the peak number of concurrent rooms needed.
Approach 2: Min-Heap Tracking End Times (Optimal) Implementation
Approach 2: Min-Heap Tracking End Times (Optimal)
public class Solution {
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!minHeap.isEmpty() && minHeap.peek() <= iv[0]) {
minHeap.poll();
}
minHeap.add(iv[1]);
}
return minHeap.size();
}
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> minHeap;
for (auto& iv : intervals) {
if (!minHeap.empty() && minHeap.top() <= iv[0]) {
minHeap.pop();
}
minHeap.push(iv[1]);
}
return minHeap.size();
}
};import heapq
class Solution:
def minMeetingRooms(self, intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[0])
heap = []
for iv in intervals:
if heap and heap[0] <= iv[0]:
heapq.heappop(heap)
heapq.heappush(heap, iv[1])
return len(heap)function minMeetingRooms(intervals) {
const starts = intervals.map(x => x[0]).sort((a, b) => a - b);
const ends = intervals.map(x => x[1]).sort((a, b) => a - b);
let rooms = 0, endIdx = 0;
for (let i = 0; i < starts.length; i++) {
if (starts[i] < ends[endIdx]) rooms++;
else endIdx++;
}
return rooms;
}Edge Cases to Watch
- Single meeting (requires exactly 1 room)
- No overlapping meetings (requires 1 room)
- Multiple simultaneous overlapping meetings (e.g. [[0, 30], [5, 10], [15, 20]]; requires 2 rooms)
- Back-to-back meetings (e.g. [1, 2] and [2, 3]; can share 1 room)
Algorithmic Pattern
View Pattern Guide →
Master the Greedy Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Greedy pattern.
How to Recognize This Pattern
- "Minimum rooms for all meetings"
- Min-heap of end times represents available room endings
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
Tags
Array Greedy Sorting Heap
Frequently Asked Questions
What is the optimal time and space complexity for Meeting Rooms II?
The optimal solution for Meeting Rooms II achieves O(n log n) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n log n) because sorting takes O(n log n), and each of the n meetings undergoes heap push/pop taking O(log n). Space complexity is O(n) to store end times in the min-heap.
How do I identify that Meeting Rooms II requires the Greedy pattern?
In technical interviews, look for key problem signals: "Minimum rooms for all meetings"; Min-heap of end times represents available room endings. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Greedy strategy.
What critical edge cases must be handled in Meeting Rooms II?
Essential edge cases to verify include: Single meeting (requires exactly 1 room); No overlapping meetings (requires 1 room); Multiple simultaneous overlapping meetings (e.g. [[0, 30], [5, 10], [15, 20]]; requires 2 rooms); Back-to-back meetings (e.g. [1, 2] and [2, 3]; can share 1 room). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Meeting Rooms II?
Meeting Rooms II is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Microsoft, Google, Lyft, Uber.