Merge Intervals
题目:
Given a collection of intervals, merge all overlapping intervals.
分析:
这题目其实考察的是sort Intervals的方法,在sort了之后就比较好处理了
java里面这个用callback function写comparator的方法实很有意思
解法:
class Solution {
/**
* @param intervals, a collection of intervals
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
// write your code here
if (intervals == null || intervals.size() <= 1) {
return intervals;
}
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
ArrayList<Interval> res = new ArrayList<Interval>();
Interval prev = intervals.get(0);
for(int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start > prev.end ) {
res.add(prev);
prev = curr;
} else {
prev.end = Math.max(prev.end, curr.end);
}
}
res.add(prev);
return res;
}
}