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
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
# using min-heap
allocation = []
intervals = sorted(intervals)
allocation.append(intervals[0][1])
heapq.heapify(allocation)
for intv in intervals[1:]:
if intv[0] < allocation[0]:
heapq.heappush(allocation, intv[1])
else:
heapq.heappushpop(allocation, intv[1])
return len(allocation)
# allocation = []
# intervals = sorted(intervals)
# allocation.append(intervals[0][1])
# #print(intervals)
# for intv in intervals[1:]:
# inserted = False
# for i in range(len(allocation)):
# #print("allocation: --", allocation, "allow: ", allocation[i], "intv : ", intv)
# if allocation[i] <= intv[0]:
# inserted = True
# allocation[i] = intv[1]
# break
# #print()
# if not inserted:
# allocation.append(intv[1])
# return len(allocation)