Merge Intervals 156

Question

Given a collection of intervals, merge all overlapping intervals.

Example

Given intervals => merged intervals:

[                     [
  [1, 3],               [1, 6],
  [2, 6],      =>       [8, 10],
  [8, 10],              [15, 18]
  [15, 18]            ]
]

Challenge

O(n log n) time and O(1) extra space.

Solution

先对list中的interval以start排序，然后依次合并有交集的interval。需要重构一个comparator。

代码如下：

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */

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
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval a, Interval b){
                return a.start - b.start;
            }
        });

        for(int i = 0; i < intervals.size() - 1; i++){
            if(intervals.get(i + 1).start <= intervals.get(i).end){
                if(intervals.get(i + 1).end > intervals.get(i).end){
                    intervals.get(i).end = intervals.get(i + 1).end;
                }else{
                    intervals.remove(i + 1);
                }
                i--;
            }
        }

        return intervals;
    }
}