• ㊗️
• 大家
• offer
• 多多！

## Problem

Given an array of meeting time intervals intervals where $intervals[i] = [start_i, end_i]$, return the minimum number of conference rooms required.

Example 1:

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


Example 2:

Input: [[7,10],[2,4]]
Output: 1


Constraints:

• $1 <= intervals.length <= 10^4$
• $0 <= start_i < end_i <= 10^6$

## Code

class Solution {
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

PriorityQueue<int[]> queue = new PriorityQueue<>(
intervals.length, (a, b) -> (a[1] - b[1])
);

queue.offer(intervals[0]);

int res = 1;

for(int i = 1; i < intervals.length; i++) {
int[] curr = intervals[i];
int[] prevMeeting = queue.poll();
if(curr[0] >= prevMeeting[1]) {
prevMeeting[1] = curr[1];
} else {
res++;
queue.offer(curr);
}
queue.offer(prevMeeting);
}

return res;
}
}

class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0

min_ends = []
intervals.sort(key= lambda x: x[0])

heapq.heappush(min_ends, intervals[0][1])

for interval in intervals[1:]:
min_end = heapq.heappop(min_ends)

if interval[0] >= min_end:
min_end = interval[1]
else:
heapq.heappush(min_ends, interval[1])

heapq.heappush(min_ends, min_end)

return len(min_ends)