关于算法:区间调度之区间合并问题

读完本文，你能够去力扣拿下如下题目：

56. 合并区间

———–

上篇文章用贪婪算法解决了区间调度问题：给你很多区间，让你求其中的最大不重叠子集。

其实对于区间相干的问题，还有很多其余类型，本文就来讲讲区间合并问题（Merge Interval）。

LeetCode 第 56 题就是一道相干问题，题目很好了解：

咱们解决区间问题的个别思路是先排序，而后察看法则。

一、思路

一个区间能够示意为 [start, end]，前文聊的区间调度问题，须要按 end 排序，以便满足贪婪抉择性质。而对于区间合并问题，其实按 end 和 start 排序都能够，不过为了清晰起见，咱们抉择按 start 排序。

显然，对于几个相交区间合并后的后果区间 x，x.start 肯定是这些相交区间中 start 最小的，x.end 肯定是这些相交区间中 end 最大的。

因为曾经排了序，x.start 很好确定，求 x.end 也很容易，能够类比在数组中找最大值的过程：

int max_ele = arr[0];
for (int i = 1; i < arr.length; i++) 
    max_ele = max(max_ele, arr[i]);
return max_ele;

二、代码

# intervals 形如 [[1,3],[2,6]...]
def merge(intervals):
    if not intervals: return []
    # 按区间的 start 升序排列
    intervals.sort(key=lambda intv: intv[0])
    res = []
    res.append(intervals[0])
    
    for i in range(1, len(intervals)):
        curr = intervals[i]
        # res 中最初一个元素的援用
        last = res[-1]
        if curr[0] <= last[1]:
            # 找到最大的 end
            last[1] = max(last[1], curr[1])
        else:
            # 解决下一个待合并区间
            res.append(curr)
    return res

看下动画就高深莫测了：

至此，区间合并问题就解决了。本文篇幅短小，因为区间合并只是区间问题的一个类型，后续还有一些区间问题。本想把所有问题类型都总结在一篇文章，但有读者反馈，长文只会珍藏不会看 … 所以还是分成小短文吧，读者有什么认识能够在留言板留言交换。

本文终，心愿对你有帮忙。