1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) return result;
PriorityQueue<Interval> queue = new PriorityQueue<Interval>(intervals.size(), new Comparator<Interval>(){
public int compare(Interval in1, Interval in2){
return in1.start-in2.start;
}
});
for (int i = 0; i < intervals.size(); i++){
queue.add(intervals.get(i));
}
while (!queue.isEmpty()){
Interval temp = queue.poll();
if (result.isEmpty()) result.add(temp);
else{
Interval last = result.get(result.size()-1);
if (isOverlapped(last, temp)){
result.remove(result.size()-1);
result.add(mergeTwoIntervals(last, temp));
}else{
result.add(temp);
}
}
}
return result;
}
private Interval mergeTwoIntervals(Interval in1, Interval in2){
return new Interval(Math.min(in1.start, in2.start), Math.max(in1.end, in2.end));
}
private boolean isOverlapped(Interval in1, Interval in2){
if (in1.start > in2.end || in1.end < in2.start) return false;
return true;
}
}
|
No comments:
Post a Comment