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 <= 1040 <= starti < endi <= 106
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
'''
Priority Queues
'''
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
used_rooms = []
intervals.sort(key=lambda t: t[0])
heapq.heappush(used_rooms, intervals[0][1])
for i in intervals[1:]:
if used_rooms[0] <= i[0]:
heapq.heappop(used_rooms)
heapq.heappush(used_rooms, i[1])
return len(used_rooms)
'''
Chronological Ordering
'''
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
used_rooms = 0
start_timings = sorted([i[0] for i in intervals])
end_timings = sorted(i[1] for i in intervals)
L = len(intervals)
end_pointer = 0
start_pointer = 0
while start_pointer < L:
if start_timings[start_pointer] >= end_timings[end_pointer]:
used_rooms -= 1
end_pointer += 1
used_rooms += 1
start_pointer += 1
return used_rooms
|