首页 > 代码库 > 253. Meeting Rooms II
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出来的第一个元素，代码如下：
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px "Helvetica Neue"; color: #454545 }</style>/**
* 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.length==0) return 0;
PriorityQueue<Interval> q = new PriorityQueue<Interval>(intervals.length,new Comparator<Interval>(){
public int compare(Interval a,Interval b){
return a.end-b.end;
}
});
Arrays.sort(intervals,new Comparator<Interval>(){
public int compare(Interval a,Interval b){
return a.start-b.start;
}
});
q.offer(intervals[0]);
for(int i=1;i<intervals.length;i++){
Interval cur = q.poll();
if(intervals[i].start<cur.end){
q.offer(intervals[i]);
}else{
cur.end = intervals[i].end;
}
q.offer(cur);
}
return q.size();
}
}
253. Meeting Rooms II