Merge Intervals

Source

• lintcode: Merge Intervals

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.

Python

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    # @param intervals, a list of Interval
    # @return a list of Interval
    def merge(self, intervals):
        # write your code here
        result=[]
        if intervals is None or len(intervals)==0:
            return result
        intervals = sorted(intervals, key=lambda tup: tup.start)

        pre = intervals[0]

        for interval in intervals:
            if pre.end<interval.start:
                result.append(pre)
                pre=interval
            else:
                #pre.start= min(pre.start, interval.start)
                pre.end = max(pre.end, interval.end)
        result.append(pre)
        return result

Java

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

class Solution {
    /**
     * @param intervals: Sorted interval list.
     * @return: A new sorted interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals==null || intervals.size()==0){
            return intervals;
        }
        List<Interval> result = new ArrayList<Interval>();

        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval l1, Interval l2){
                return l1.start-l2.start;
            }
        });

        Interval pre = intervals.get(0);

        for(int i=1; i<intervals.size(); i++){
            Interval interval = intervals.get(i);
            if(pre.end<interval.start){
                result.add(pre);
                pre=interval;
            }
            else{
                //pre.start=Math.min(pre.start, interval.start);
                pre.end=Math.max(pre.end, interval.end);
            }
        }
        result.add(pre);
        return result;
    }
}