Merge Intervals

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].

思路

先按照Interval.start进行升序排列，如果前一个front,后一个behind。如果behind.end < front.start不用管，behind.end >= front.end 删除front。behind.end > front.start && behind.end < front.end合并

 1 /**
 2  * Definition for an interval.
 3  * public class Interval {
 4  *     int start;
 5  *     int end;
 6  *     Interval() { start = 0; end = 0; }
 7  *     Interval(int s, int e) { start = s; end = e; }
 8  * }
 9  */
10 public class Solution {
11     public List<Interval> merge(List<Interval> intervals) {
12         Collections.sort(intervals, new Compare());
13         boolean isMerge = false;
14         while(true){
15             isMerge = false;
16             for(int i = 0; i < intervals.size() - 1; i++){
17                 Interval behind = intervals.get(i);
18                 Interval front    = intervals.get(i + 1);
19                 if(behind.end < front.start)                                    //后面一个end小于前面的start
20                     continue;
21                 else if(behind.end >= front.end)                                //后面一个end大于等于前面的end
22                 {
23                     intervals.remove(i + 1);
24                     isMerge = true;
25                 }
26                 else if(behind.end < front.end && behind.end >= front.start){    //后面的end在前面的start和end中间，合并
27                     behind.end = front.end;
28                     intervals.remove(i + 1);
29                     isMerge = true;
30                 }//else if
31             }//for
32             if(!isMerge)
33                 break;
34         }
35         
36         return intervals;
37     }
38 
39 }
40 class Compare implements Comparator<Interval>{
41 
42     @Override
43     public int compare(Interval o1, Interval o2) {
44         if(o1.start < o2.start)
45             return -1;
46         else if(o1.start > o2.start)
47             return 1;
48         else
49             return 0;
50     }
51 }