一. 正常的方法， PriorityQueue

1.先把intervals按照开始的时间排序

2. 建一个PriorityQueue，按照结束的时间排序，这样每次poll()出来的都是最早结束的那个会议，开始先把第一个开始的会议放进去

3. 对于每一个intervals，即下一个开始的会议

　　earliestEnd = pq.poll()即最早结束会议

　　如果这个会议的开始时间，比最早结束的那个会议的结束之前要晚（不需要新的room，把两个meeting合并起来）：

　　　　earliestEnd.end = intervals[i].end

　　否则(即需要新的房间)

　　　　pq.offer(intervals[i])

　　把earliestEnd放回去: pq.offer(earliestEnd)

4.返回pq的size

1     public int minMeetingRooms(Interval[] intervals) { 2         if(intervals.length == 0) { 3             return 0; 4         } 5         Arrays.sort(intervals, new Comparator
     
      (){ 6             public int compare(Interval o1, Interval o2) { 7                 return o1.start - o2.start; 8             } 9         });10         PriorityQueue
      
        pq = new PriorityQueue
       
        (intervals.length, new Comparator
        
         () {11             public int compare(Interval o1, Interval o2) {12                 return o1.end - o2.end;13             }14         });15         pq.add(intervals[0]);16         for(int i = 1; i < intervals.length; i++) {17             Interval earliestEnd = pq.poll();18             if(earliestEnd.end <= intervals[i].start) {19                 earliestEnd.end = intervals[i].end;20             } else {21                 pq.offer(intervals[i]);22             }23             pq.offer(earliestEnd);24         }25         return pq.size();26     }
        
       
      
     

需要注意的是：

该算法的时间复杂度是O(nlogn)。

PriorityQueue的时间复杂度：

　　add, poll, offer都是logn.因为用了quickSort排序

　　contains是O(n)，线性查找

　　poll, peek之类的都是O(1)

 

二. 超级方法

1. 把所有会议的开始时间都单独拎出来建一个数组，排序

2. 把会议的结束时间都拎出来建一个数组，排序

我的理解是按照时间轴走一遍，比如我们有这样5个会议

[0,30],[5,10],[10,15],[15,20],[25,35]

所有开始时间的排序是：

0,5,10,15,25

结束时间排序是

10,15,20,30,35

我们按照开始时间走

start[1]:在第5分钟，我们有2个会议开始了，但是第一个结束的会议到10分钟才结束，所以room++需要2个会议室

start[2]:到第10分钟，我们有3个会议开始了，但是有一个会议在10分的时候结束了，所以我们还是只有2个会议Ongoing，下一个结束时间是15分

start[3]:到第15分钟，又开了一个新的会议，变成3个会议开始，但是15分的时候有一个会议结束了，还是只有2个会议Ongoing，下一个结束时间是20分钟

start[4]:到第25分钟, 又开了一个新的会议，变成3个会议开始，但是20分的时候有一个会议结束了，还是只有2个会议Ongoing

已经没有新的会议的，最后一个会议什么时候结束不重要了

返回room的数量

 

1     public int minMeetingRooms(Interval[] intervals) { 2         if(intervals.length == 0) { 3             return 0; 4         } 5         int len = intervals.length; 6         int[] start = new int[len]; 7         int[] end = new int[len]; 8         for(int i = 0; i < len; i++) { 9             start[i] = intervals[i].start;10             end[i] = intervals[i].end;11         }12         Arrays.sort(start);13         Arrays.sort(end);14         int room = 1;15         int nextEndTime = 0;16         for(int i = 1; i < len; i++) {17             if(start[i] < end[nextEndTime]) {18                 room++;19             } else {20                 nextEndTime++;21             }22         }23         return room;24     }

时间复杂度是O(nlogn)。因为Arrays.sort()的时间复杂度是这个