leetcode56：合并区间

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*
    本题是判断区间重叠后，需要进行区间合并。
    先排序，让所有的相邻区间尽可能地重叠在一起，
    按左边界，或者右边界排序都可以，处理逻辑稍有不同。

    时间复杂度：O(nlogn)
        其中 n 是区间的数量。
        排序的时间复杂度为 O(nlog⁡n)，遍历区间的时间复杂度为 O(n)。
    空间复杂度：O(n)
        答案数组存储结果列表。
*/
class Solution_0 {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }

        sort(intervals.begin(), intervals.end(), 
        [](const vector<int>& x, const vector<int>& y) {
            if (x[0] != y[0]) {
                return x[0] < y[0];
            }
            return x[1] < y[1];
        });

        vector<vector<int>> res;
        int l = intervals[0][0], r = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (r < intervals[i][0]) {
                // 区间不重叠
                res.push_back({l, r});
                l = intervals[i][0], r = intervals[i][1];
            } else {
                // 区间重叠，进行合并
                r = max(r, intervals[i][1]);
            }
        }
        // 将最后一个区间添加到结果
        res.push_back({l, r});

        return res;
    }
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<vector<int>>> intervals_case = {
        {{1,3}, {2,6}, {8,10}, {15,18}},
        {{1,4}, {4,5}}
    };
    
    for (auto& intervals : intervals_case) {
        cout << "Input: ";
        printArray(intervals);
        cout << endl;

        vector<vector<int>> result = solution.merge(intervals);
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }

    return 0;
}