0253-meeting-rooms-ii¶
Try it on leetcode
Description¶
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
Solution(Python)¶
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
#
# intervals = [[0,30],[5,10],[15,20]]
# 0 - 30 room = 1
# 5 10 room = 2
# 15 - 20 = 1
# sort by start
# build heap of end times
# if s < heap[-1]
# add heap
# else:
# heap pop
# i = 0; heap = [30]; room = 1
# i =1 ; 0 < 30 ; heap = [10, 30]; room = 2
# i =2 ; 10 < 15; heap = [15, 30]; room = 2
#
# alteenatuve way process start and end arrays
# start = [0, 5, 15]
# end = [30, 10 ,20]
# process chroonogoligcal order
# start < end
# increase room count
# else:
# decrease room count
# start = 0; end = 30; o < 30; room = 1
# s = 5; e = 30; room = 2
# s = 15; e = 20; room = 3
#
start = sorted([interval[0] for interval in intervals])
end = sorted([interval[1] for interval in intervals])
n = len(start)
i = 0
j = 0
rooms = 0
min_rooms = 0
while i < n:
if start[i] < end[j]:
rooms += 1
i += 1
else:
rooms -= 1
j+=1
min_rooms = max(min_rooms, rooms)
return min_rooms