题目描述

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

样例

示例 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] 可被视为重叠区间

算法1

(贪心) $O(nlogn)$

思路

• 将区间按照左端点排好序
• 维护一个区间，枚举时更新
  • 有交集 更新区间的右端点为 交集两区间的右端点的最大值
  • 无交集 加入答案，更新区间
• 注意对最后一个区间的讨论

C++ 代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        vector<vector<int>> res;

        int st = -2e9, ed = -2e9;
        for(int i = 0; i < n; i++) // 枚举区间
        {
            // 无交集
            if(ed < intervals[i][0])
            {
                if(st != -2e9) res.push_back({st, ed});
                st = intervals[i][0], ed = intervals[i][1];
            }
            // 有交集
            else ed = max(ed, intervals[i][1]);
        }

        if(st != -2e9)  res.push_back({st, ed});  // 把最后一段加上

        return res;
    }
};

用auto 简化代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& segs) {
        sort(segs.begin(), segs.end());
        vector<vector<int>> res;

        int st = -2e9, ed = -2e9;
        for(auto seg : segs)
        {
            if(ed < seg[0])
            {
                if(st != -2e9) res.push_back({st, ed});
                st = seg[0], ed = seg[1];
            }
            else ed = max(ed, seg[1]);
        }

        if(st != -2e9) res.push_back({st, ed});

        return res;
    }
};

和 acwing 803. 区间合并 对比记忆

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());
    // 维护区间 左右端点初始化
    int st = -2e9, ed = -2e9;  

    for(auto seg : segs)
    {
        if(ed < seg.first)  // 无交集
        {
            if(st != -2e9) res.push_back({st, ed}); // 没交集 且不是初始区间
            st = seg.first, ed = seg.second;       // 更新为下一待合并的区间
        }
        else 
            ed = max(ed, seg.second);             // 把有交集 和 包含在内的情况一起处理了
    }

    // 【最后这里判断容易遗忘】
    if(st != -2e9) res.push_back({st, ed});       // 最后的区间也要加入答案 判断是为了防止输入空数组

    segs = res;
}

int main()
{
    cin >> n;
    // 输入处理 区间的左右端点
    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;


    return 0;
}