【Leetcode】156. Merge Intervals

156. Merge Intervals

Description

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.

虽然它本来无序，但我们可以将它根据 start 值的大小进行排序，可以使用 Collections 类中的 sort 方法对 List 进行排序。排完之后，就可以对集合内的区间进行合并了。

申请一个新的集合，再用一个循环，将排好序的区间两两比较，如果无需合并，则将前者加入新的集合，后者继续与后面的区间比较合并。代码如下：

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

public class Solution {
    /**
     * @param intervals: interval list.
     * @return: A new interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        // write your code here
        if(intervals == null || intervals.size() == 0) return intervals;
        List<Interval> result = new ArrayList<>();
        Collections.sort(intervals, new IntervalComparator());   
        Interval last = intervals.get(0);
        for(int i=1;i<intervals.size();i++){
            Interval cur = intervals.get(i);
            if(last.end >= cur.start){
                last.end = Math.max(last.end,cur.end);
            }else{
                result.add(last);
                last = cur;
            }
        }
        result.add(last);
        return result;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}