MediumBlind75ArraySortHeapGreedy
Meeting Rooms II
Given an array of meeting time intervals, find the minimum number of conference rooms required.
Examples
Input
intervals = [[0,30],[5,10],[15,20]]
Output
2
Room 1: [0,30], Room 2: [5,10] and [15,20].
Input
intervals = [[7,10],[2,4]]
Output
1
Only one room is needed since the meetings don't overlap.
Constraints
- •
1 <= intervals.length <= 10^4 - •
0 <= starti < endi <= 10^6
Approaches
For each meeting, count how many other meetings it overlaps with.
CodeT: O(n^2) | S: O(1)
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
count = 0
for i in range(len(intervals)):
overlap = 0
for j in range(len(intervals)):
if i != j and intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
overlap += 1
count = max(count, overlap + 1)
return countUse a min heap to track end times of ongoing meetings.
CodeT: O(n log n) | S: O(n)
import heapq
def min_meeting_rooms(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.heapreplace(heap, end)
else:
heapq.heappush(heap, end)
return len(heap)Use two sorted arrays for start and end times.
Diagram
intervals = [[0,30],[5,10],[15,20]]
Starts: [0,5,15], Ends: [10,20,30]
start=0: 0<10, rooms=1, max=1
start=5: 5<10, rooms=2, max=2
start=15: 15>=10, end_ptr=1, 15<20, rooms=3... wait
Actually: start=15: 15>=10(end_ptr=0), end_ptr=1
rooms stays 2 (not incremented)
Result: 2
CodeT: O(n log n) | S: O(n)
def min_meeting_rooms(intervals):
if not intervals:
return 0
starts = sorted(i[0] for i in intervals)
ends = sorted(i[1] for i in intervals)
rooms = 0
max_rooms = 0
end_ptr = 0
for start in starts:
if start < ends[end_ptr]:
rooms += 1
max_rooms = max(max_rooms, rooms)
else:
end_ptr += 1
return max_roomsComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - Check All Overlaps | O(n^2) | O(1) | For each meeting, count how many other meetings it overlaps with. |
| Min Heap | O(n log n) | O(n) | Use a min heap to track end times of ongoing meetings. |
| Chronological Order | O(n log n) | O(n) | Use two sorted arrays for start and end times. |
Brute Force - Check All Overlaps
T: O(n^2)S: O(1)
For each meeting, count how many other meetings it overlaps with.
Min Heap
T: O(n log n)S: O(n)
Use a min heap to track end times of ongoing meetings.
Chronological Order
T: O(n log n)S: O(n)
Use two sorted arrays for start and end times.
Common Mistakes
Not sorting the intervals first
Using a max heap instead of a min heap
Not handling empty input