253. Meeting Room II

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

Analyzation:

We may keep a min heap of all conference ending time and use the size to indicate how many rooms we need.

We may iterate the conference timing array, for each iteration, we compare the starting time with the earlist ending time E up to now(which is peek of the heap), if current starting time is greater than E, then we pop the min ending time(imaging the previous conference is finished and we hold current conference in the idle room).

We continue steps above, the size of the heap will represents how many rooms we need.

Solution:

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0){
            return 0;
        }
        Comparator<int[]> entity = new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        };

        Arrays.sort(intervals, entity);

        PriorityQueue<Integer> store = new PriorityQueue<>(intervals.length, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return a - b;
            }
        });

        for(int i = 0; i < intervals.length ; i++){
            if(!store.isEmpty() && store.peek() <= intervals[i][0]) store.poll();
            store.add(intervals[i][1]);
        }
        return store.size();
    }
}