# 253. Meeting Rooms II

Given an array of meeting time intervals `intervals` where `intervals[i] = [starti, endi]`, return the minimum number of conference rooms required.

Example 1:

```Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
```

Example 2:

```Input: intervals = [[7,10],[2,4]]
Output: 1
```

Constraints:

• `1 <= intervals.length <= 104`
• `0 <= starti < endi <= 106`

Python Solution 1: time complexity O(n log(n)) (Beat 53.89%)
Sort all time points and label the start and end points. Move a vertical line from left to right.
When it meets a start point, curr_rooms += 1. When it meets an end point, curr_rooms -= 1.
(if there is a tie: put end point before start point). Update the maximal occupied rooms during the move.

``````    def minMeetingRooms(self, intervals):
lst = []
for start, end in intervals:
lst.append((start, 1))
lst.append((end, -1))
lst.sort()
res, curr_rooms = 0, 0
for t, n in lst:
curr_rooms += n
res = max(res, curr_rooms)
return res
``````

Python Solution 2: time complexity O(n * log(max(l_heap))) (Beat 95.82%, max(l_heap) <= n)

``````    def minMeetingRooms(self, intervals):
intervals.sort(key = lambda x: x)
res = 0
heap, heap_size = [], 0
for interval in intervals:
while heap and heap <= interval:
heapq.heappop(heap)
heap_size -= 1
heapq.heappush(heap, interval)
heap_size += 1
res = max(res, heap_size)
return res``````
Scroll to Top