253. Meeting Rooms 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.

For example,
Given[[0, 30],[5, 10],[15, 20]],
return2.

Solution:

1. sort array with start time
2. using a minheap of end time to store the interval values, the top of the heap is the one who finishes the earliest
3. if the start time >= top of the minheap, no need to have a new room, continues using the room for the top of the heap, update the top of the heap
4. else, need a new room, add a new interval into the heap
5. heap size is the room number we need

public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0){
            return 0;
        }    

        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
        });

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

        minHeap.offer(intervals[0]);
        for(int i = 1; i < intervals.length; i++){
            Interval top = minHeap.poll();
            if(top.end <= intervals[i].start){
                top.end = intervals[i].end;
            }else{
                minHeap.offer(intervals[i]);
            }
            minHeap.offer(top);
        }

        return minHeap.size();
    }