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]],
return 2.

此题非常经典，用了两种自定义排序，第一种是将原来数组按照start从小到大排列。第二种设置一个优先队列按照end从小到大进行排序。将排好序的数组的第一个元素插入优先队列中。将优先队列中的元素的end和数组后面的元素start进行比较，如果有重叠部分，则将数组后面的元素插入优先队列中，然后原优先队列中的元素也插入进去，接下来不断进行比较即可，如果没有重叠部分后将下一个元素的end值赋值给优先队列中的poll出来的第一个元素，代码如下：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals==null||intervals.length==0) return 0;
        Comparator<Interval> comp = new Comparator<Interval>() {
            public int compare(Interval i1,Interval i2) {
                return i1.start-i2.start;
            }
        };
        Arrays.sort(intervals,comp);
        PriorityQueue<Interval> pq = new PriorityQueue<>(new Comparator<Interval>(){
            public int compare(Interval i1,Interval i2){
                return i1.end-i2.end;
            }
        });
        pq.offer(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            Interval interval = pq.poll();
            if(intervals[i].start>=interval.end){
                interval.end = intervals[i].end;
            }else{
                pq.offer(intervals[i]);
            }
            pq.offer(interval);
        }
        return pq.size();
    }
}
//the run time nlogn,the space complexity could be O(n);