253. Meeting Rooms II

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

Solution:

为了开这些会至少要多少个房间

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int result = 0;

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        // [0,30], [5,10], [15, 20] 

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // minHeap


        for (int[] interval : intervals){
            // [0, 30] // [5, 10] [15, 20]
            if (!pq.isEmpty() && pq.peek() <= interval[0]){
                // 30, 30 < 5 // 5 < 15
                pq.poll();
            }

            pq.offer(interval[1]);
            // [30, 5]
        }

        return pq.size();

    }
}
// TC:O(nlogn)
// SC:O(n)