253. Meeting Rooms II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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)