题解 | #合并区间#

思路：

先按区间头排序，再遍历区间，用目前结果区间的末尾和当前区间头比较，如果有交叉就要更新区间末尾，否则插入新区间。

关键是排序这部分的代码，python很简单，sort或sorted。

java和c++引用一下官方的比较代码：

Collections.sort(intervals, newComparator<Interval>() {
	publicintcompare(Interval o1, Interval o2) {
		if(o1.start != o2.start)
			returno1.start - o2.start;
		else
	returno1.end - o2.end;
	}
});

staticbool cmp(Interval &a, Interval &b) {
	returna.start < b.start;
}
sort(intervals.begin(), intervals.end(), cmp);

from functools import cmp_to_key
# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        ret = []
        if len(intervals) == 0:
            return ret

        # 按照区间起点升序排序
        # 注意这里不是二维列表，是自定义数据结构，不能x[0]获取
        intervals.sort(key=lambda x: x.start)
        ret.append(intervals[0])

        # 遍历
        for i in intervals:
            # 末尾小于前者就是区间有重叠，更新区间尾值，
            if i.start <= ret[-1].end:
                ret[-1].end = max(i.end, ret[-1].end)
            # 否则插入新区间
            else:
                ret.append(i)

        return ret