56、合并区间 (Merge Intervals)

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路：
*  根据对象的start 升序排序
*  遍历对象列表
*  如果当前结果列表最后一个元素end比下一个元素的start小   则把下一个加入到结果列表
*  否则 将当前结果列表中最后一个元素的end赋值 = max(res.get(last()).end, current.end)

java

public class Solution {

    public class Interval {
          int start;
          int end;
          Interval() { start = 0; end = 0; }
          Interval(int s, int e) { start = s; end = e; }
     }


    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public List<Interval> merge(List<Interval> intervals) {

        // 根据start排序
        Collections.sort(intervals, (x,y) -> (x.start - y.start));
        LinkedList<Interval> res = new LinkedList<>();
        for (Interval inerval: intervals
             ) {
            if (res.isEmpty() || res.peekLast().end < inerval.start) {
                res.addLast(inerval);
            } else {
                res.peekLast().end = Math.max(inerval.end, res.peekLast().end );
            }
        }
        return res;
    }


}

python

# Definition for an interval.
class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        intervals.sort(key=lambda x : x.start)
        res = []
        for interval in intervals:
            if len(res) <= 0 or res[len(res)-1].end < interval.start:
                res.append(interval)
            else:
                res[len(res)-1].end  = max(res[len(res)-1].end, interval.end)
        return res