253. Meeting Rooms II (1)

Link

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find 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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

class Solution {
    public int minMeetingRoom(int[][] intervals) {
        
        //need to sort before checking, otherwise will misjudge the ovelap case
        //ex: {[1,4][0,0]} -> misjude the [0,0] is overlapped with [1,4]
        Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));
        
        if(intervals.length <= 1){
            return intervals.length;
        }
        int count = 1;
        PriorityQueue<Integer> pq = new PriorityQueue<>(); //min heap
        //保證每次peek/toll出來是最快可以結束會議的時間
        for(int i = 1; i < intervals.length; i++){
            if(pq.isEmpty)
            {
                pq.offer(intervals[i][1]); //put the end time to min heap
            }
            else if( pq.peek < intervals[i][0] ){
                //上場會議的結束時間比目前這場開始時間還早
                //不會用到會議室
                pq.poll(); //上一場已經不影響可以移出heap
                pq.offer(intervals[i][1]);
            }
            else if(pq.peek > intervals[i][0]){
                count++;
                pq.offer(intervals[i][1]);
            }
        }
        return count;
    }
}

Time complexity: O(nlogn)