【leetcode】【剑指offer Ⅱ】074. 合并区间

问题描述：

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

核心思路：

• 区间问题，该题是扫描线问题。
• 该题有排序解法，还有差分数组解法。
  • 差分思想其实就是扫描线思想。
• 差分数组的解法其实很简单，首先要清楚，区间格式的数据都有起始位置和结束位置：
  • 假设一个区间为一个会议室订阅时间，因此可以认为单个区间就占用一间会议室，多个区间如果产生重叠，则必定存在某个子区间会占用多余一间会议室。
  • 差分数组的思路就是在区间起始位置添加一间会议室，在区间结束位置减少一间会议室，相当于是在差分数组中记录起始时间的信息与结束时间的信息。
  • 将所有区间的信息存入差分数组之后，再遍历差分数组将起始位置的信息传递给结束位置的信息（所谓的扫描线思想）。
• 差分数组思想的基本应用都很直白，都是多个区间之间的交互，同时实现上很简单，即可以用数组来实现，也可以用有序哈希表来实现。
  • 差分数组其实和后缀数组有相似之处，一个是求相邻数值间的差值，一个是求相邻数值间的求和。

代码实现：

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        map<int, int> mm;
        for(auto& inter : intervals)
            ++mm[inter[0]], --mm[inter[1]];
        vector<vector<int>> ans;
        int l, r;
        int pre = 0, sum = 0;
        for(auto& [idx, cur] : mm)
        {
            if(pre == 0) l = idx; // 前一个时间点为0间会议室，当前无论是什么，都是新区间的开始
            sum += cur;
            if(sum == 0) r = idx, ans.push_back({l, r}); // 当前是0间会议室，则说明是区间的结束
            pre = sum;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21