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.
Greedy, Sort
public int minMeetingRooms(Interval[] intervals) {
if(intervals.length == 0) return 0;
int min = 0;
Set<Interval> set = new LinkedHashSet();
Arrays.sort(intervals, new Comparator<Interval>(){
public int compare(Interval i1, Interval i2){
if(i1.start == i2.start) return 0;
else return i1.start > i2.start ? 1 : -1;
}
});
for(Interval i : intervals)
set.add(i);
while(!set.isEmpty()){
min ++;
Iterator<Interval> iter = set.iterator();
Interval head = iter.next();
Interval prev = head;
while(iter.hasNext()){
Interval curr = iter.next();
if(prev.end <= curr.start){
iter.remove();
prev = curr;
}
}
set.remove(head);
}
return min;
}