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].
|
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 { /**There is not special algorithm for this problem.<br> * 1. sort the intervals according to the start point * 2. linear scan the sorted intervals and then merge them together * * @param intervals --List of Intervals. * @return --List of Intervals, in which no intervals have overlaps * @author Averill Zheng * @version 2014-06-12--world cup opening day * @since JDK 1.7 */ public
List<Interval> merge(List<Interval> intervals) { List<Interval> result = new
ArrayList<Interval>(); if(!intervals.isEmpty()){ Collections.sort(intervals, new
IntervalComparator()); int
length = intervals.size(); int
start = intervals.get(0).start; int
end = intervals.get(0).end; for(int
i = 1; i < length; ++i){ Interval current = intervals.get(i); if(current.start <= end) end = Math.max(end, current.end); else{ result.add(new
Interval(start, end)); start = current.start; end = current.end; } } result.add(new
Interval(start, end)); } return
result; }}class
IntervalComparator implements
Comparator<Interval>{ public
int compare(Interval a, Interval b){ return
Integer.compare(a.start, b.start); }} |
leetcode--Merge Intervals,布布扣,bubuko.com
原文：http://www.cnblogs.com/averillzheng/p/3785015.html