Meeting Rooms II
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Salesforce
Problem
Given an array of meeting time intervals, find the minimum number of conference rooms required. This is a classic scheduling problem that tests heap and greedy skills.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Uber | Medium | View all Uber questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Sort meetings by start time. Use a min-heap to track end times of ongoing meetings.
For each meeting, check if the earliest ending meeting finishes before this one starts. If so, reuse that room (pop from heap).
The heap size at any point is the number of rooms simultaneously in use. Track the maximum heap size.
Why it works: the heap always contains the end times of currently occupied rooms. If the earliest end time <= current start, that room is free.
Visual walkthrough for [[0,30],[5,10],[15,20]]:
Sort: same order.
Meeting [0,30]: heap=[30]. Rooms=1.
Meeting [5,10]: 30>5, can't reuse. heap=[10,30]. Rooms=2.
Meeting [15,20]: 10<=15, reuse room. Pop 10. heap=[20,30]. Rooms=2.
Result: 2 rooms.
Alternative: sweep line. Create events (+1 at start, -1 at end). Sort by time (end before start for ties). Track max concurrent.
Edge cases: no meetings (0 rooms), all meetings overlap (n rooms), no overlaps (1 room).
Optimal Approach
Step 1: Sort intervals by start time.
Step 2: Use a min-heap of end times.
Step 3: For each meeting [start, end]:
If heap[0] <= start, pop (room is free, reuse it).
Push end onto heap.
Step 4: Return len(heap) — the max rooms used.
Time: O(n log n) — sort + heap operations. Space: O(n).
What Trips People Up in Real Interviews
Confusing this with Meeting Rooms I. That problem asks if all meetings can attend (no overlaps). This one asks for the minimum number of rooms.
Sorting by end time instead of start time. You need to process meetings in start-time order to correctly count concurrent meetings.
Not reusing rooms. When a meeting ends before the next one starts, that room is free. Pop from the heap.
Forgetting to track the maximum heap size. The answer is the maximum number of simultaneous meetings, not the final heap size.
Using a max-heap instead of a min-heap. A max-heap tracks the latest ending meeting — useless for room reuse. A min-heap gives you the earliest ending meeting to check availability.
Solution Code
import heapq
def minMeetingRooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)Frequently Asked Questions
What is the Meeting Rooms II problem?
Given an array of meeting time intervals, find the minimum number of conference rooms required. This is a classic scheduling problem that tests heap and greedy skills.
How do you solve Meeting Rooms II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Meeting Rooms II?
Meeting Rooms II is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Salesforce. It is a medium difficulty problem.
What are common mistakes on Meeting Rooms II?
- Confusing this with Meeting Rooms I. That problem asks if all meetings can attend (no overlaps). This one asks for the minimum number of rooms.
- Sorting by end time instead of start time. You need to process meetings in start-time order to correctly count concurrent meetings.
- Not reusing rooms. When a meeting ends before the next one starts, that room is free. Pop from the heap.
- Forgetting to track the maximum heap size. The answer is the maximum number of simultaneous meetings, not the final heap size.
- Using a `max-heap` instead of a `min-heap`. A `max-heap` tracks the latest ending meeting — useless for room reuse. A `min-heap` gives you the earliest ending meeting to check availability.