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].
https://leetcode.com/problems/merge-intervals/
Remenber Collections.sort(List list, Comparator<? super T> c) and the way to implement Comparator.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public List<Interval> merge(List<Interval> intervals) {
if(intervals == null || intervals.size() <= 1) return intervals;
List<Interval> result = new ArrayList<Interval>();
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
if(a.start < b.start) return -1;
else if(a.start > b.start) return 1;
else return 0;
}
});
Interval t = intervals.get(0);
for(int i = 1; i < intervals.size(); ++i) {
Interval cur = intervals.get(i);
if(cur.start > t.end) {
result.add(t);
t = cur;
} else if(cur.end > t.end)
t.end = cur.end;
}
result.add(t);
return result;
}
|