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
- code
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort()
rooms = [intervals[0][1]] # end time
for i in range(1, len(intervals)):
cur_start, cur_end = intervals[i]
for r_index in range(len(rooms)):
if cur_start >= rooms[r_index]:
rooms[r_index] = cur_end
break
else:
rooms.append(cur_end)
return len(rooms)
- code
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort()
rooms = [intervals[0][1]] # end time
for i in range(1, len(intervals)):
cur_start, cur_end = intervals[i]
if cur_start >= rooms[0]: # only need to compare to the existed minimum end time
heapq.heappop(rooms)
heapq.heappush(rooms, cur_end)
return len(rooms)
- code
class Solution {
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> rooms = new PriorityQueue<>();
for (int[] interval: intervals){
rooms.offer(interval[1]);
if (interval[0] >= rooms.peek()){
rooms.poll();
}
}
return rooms.size();
}
}