题目
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
class Solution {
public List<Interval> merge(List<Interval> intervals) {
if(intervals.size() <= 1) return intervals;
List<Interval> ans = new LinkedList<Interval>();
// sort by start time
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval c1, Interval c2) {
if (c1.start > c2.start) return 1;
if (c1.start < c2.start) return -1;
return 0;
}
});
int left = 0, right;
while(left < intervals.size()) {
Interval i1 = intervals.get(left);
for(right = left + 1; right < intervals.size(); right++) {
Interval i2 = intervals.get(right);
if(i1.end < i2.start) break;
i1.end = Math.max(i1.end, i2.end);
}
ans.add(i1);
left = right;
}
return ans;
}
}
