区间合并问题

摘要: 本文我们以力扣 56 来看一下区间合并问题的各种解法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文我们系统串讲一下区间合并问题。这个问题有很多解法，每个解法都是主流经典算法。同时区间也是在业务场景中需要频繁处理的对象，涉及到区间的常见操作有： 插入，删除，合并，交集，并集等等。因此本题值得研究，涉及的算法如下：

• 转换成图的连通性问题
• 给区间染色
  • 优化1: 离散化
  • 优化2: 前缀和
• 扫描线算法
• 贪心排序

---

$1 题目

• 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

提示：

1 <= intervals.length <= 1e4
intervals[i].length == 2
0 <= starti <= endi <= 1e4

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

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

$2 题解

算法1 : 图的连通分量

两个区间想要合并，则两个区间有重合的部分。

将每个线段视为一个点，若两个线段有重合的部分，则视为两个点有连边。然后统计每个连通分量的 [l, r]。

此算法时间复杂度主要在于边的数量。

算法2 : 染色统计，离散化，前缀和

区间覆盖的想法，数轴上某个位置 i 被区间列表中的区间覆盖过，则它一定会出现在结果中。对该点进行染色标记。

每来一个新区间[l, r]，都用固定的一个颜色把区间中的点 i 进行一次染色。染色完成后进行统计，连续被染色的点构成的区间即为合并后的大区间。

此算法时间复杂度 O(NL)，L 是区间长度。如果 L 为 INT 范围，则 L 可以达到 2e9 级别。

很多题目需要用到此法，例如求区间覆盖度。

优化1 : 离散化

只有右边界的地方才有划分。处理现在已经是边界的位置，其它位置不重要，所有只需要考虑现在已经有的边界点。这是离散化的思想。

将所有区间的 l, r 放入一个 vector，然后进行排序。

例如所有区间 ： [[1, 3],[2, 4],[5, 7]]，离散化后得到端点列表：[1,2,3,4,5,7]，可以发现 6 是不需要的，因为肯定不是边界。
此后在新数轴 [1,2,3,4,5,7] 上画染色。

离散化的相关知识参考 力扣493-离散化,权值线段树,权值树状数组

该算法时间复杂度为 $O(N^{2})$

优化2 : 前缀和

利用前缀和与差分的关系，利用维护差分的思想维护区间的染色。

来了一个新区间，对区间内各个点 i 进行染色，是一次区间修改，这个区间修改可以通过维护差分的方式来维护 [l, r]，前缀和与差分相关的知识参考 力扣303-前缀和

统计结果时，对区间内每个元素做前缀和，每个位置就都会从差分恢复成元素，就可以知道每个区间的覆盖度了。

算法3 : 扫描线

如图所示，假想一条垂直的投影线从左向右扫描。记事件 Event 为遇到了区间的端点，用一个计数器 sum 维护遇到的左端点和右端点，当遇到左端点时，sum += 1，遇到右端点时，sum -= 1

当 sum 从 1 变为 0 时，说明当前事件的位置是当前合并区间的右端点，当 sum 从 0 变为 1 时，说明当前事件的位置是新的合并区间的左端点。

代码(C++)

struct Event
{
    int idx;
    int kind; // 0: 左端点，1: 右端点
    Event(int idx, int kind):idx(idx),kind(kind){}
};

struct Cmp
{
    bool operator()(const Event& e1, const Event& e2) const
    {
        if(e1.idx == e2.idx)
            return e1.kind < e2.kind;
        return e1.idx < e2.idx;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<Event> events;
        for(const vector<int>& interval: intervals)
        {
            events.push_back(Event(interval[0], 0));
            events.push_back(Event(interval[1], 1));
        }
        sort(events.begin(), events.end(), Cmp());
        vector<vector<int>> result;
        int sum = 0;
        for(const Event& e: events)
        {
            if(sum == 0)
                result.push_back({e.idx, -1});
            if(e.kind == 0)
                ++sum;
            else
                --sum;
            if(sum == 0)
                result.back()[1] = e.idx;
        }
        return result;
    }
};

算法4 : 贪心排序

将列表中的区间按照左端点升序排序得到 ranges。枚举 ranges 中的区间。第一个区间 ranges[0] 的左端点为第一个合并区间的左端点，在枚举 ranges[1..n-1] 时，始终维护当前合并区间的右端点。

假设当前枚举的区间为 ranges[i], 当前的合并区间的右端点为 r。

如果 ranges[i] 的左端点比 r 大，则此后的各个区间端点也会比 r 大，

所以当前合并区间不会再变大了，此时将当前合并区间更新进答案，然后以当前枚举的区间 ranges[i] 建立新的当前合并区间。

如果 ranges[i] 的左端点小于等于 r，则整个 ranges[i] 的范围都属于当前的合并区间，此时更新当前的合并区间右端点。r = max(r, ranges[i].r)。

代码(C++)

class Solution_2 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.empty()) return vector<vector<int> >();
        int n = intervals.size();
        if(n == 1) return intervals;
        sort(intervals.begin(), intervals.end(), compare);
        vector<vector<int> > results;
        for(const auto& interval: intervals)
        {
            if(results.empty() || interval[0] > results.back()[1])
                results.push_back(interval);
            else
                results.back()[1] = max(results.back()[1], interval[1]);
        }
        return results;
    }

private:
    static bool compare(const vector<int>& interval1, const vector<int>& interval2)
    {
        return interval1[0] < interval2[0];
    }
};

$4 区间操作

区间操作主要包括插入，合并，删除，选择等。相关的问题主要针对区间的左右端点设计算法，常用以下几种算法：

1. 双指针算法，滑窗算法
2. 贪心算法，维护贪心的算法和数据结构有排序，堆，平衡树
3. 扫描线算法，把区间左右端点抽象成事件

• 区间上的问题汇总

---