LeetCode 算法：合并区间c++

原题链接🔗：合并区间
难度：中等⭐️⭐️

题目

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

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

提示：
1 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

题解

贪心算法

题解：

合并区间问题是一个典型的贪心算法问题，其核心思想是将区间按照开始时间进行排序，然后依次合并重叠的区间。以下是解决这个问题的详细步骤：

排序：首先，将所有区间按照每个区间的开始时间进行升序排序。如果开始时间相同，则可以按照结束时间进行升序排序，但通常这并不影响最终结果。

初始化：创建一个结果数组result，用于存储合并后的区间。将排序后的区间数组的第一个区间添加到result中。

遍历和合并：遍历排序后的区间数组，对于每个区间，执行以下操作：

如果当前区间的开始时间小于或等于result中最后一个区间的结束时间，说明这两个区间有重叠，需要合并。将result中最后一个区间的结束时间更新为当前区间的结束时间和result中最后一个区间的结束时间中的较大者。
如果当前区间的开始时间大于result中最后一个区间的结束时间，说明这两个区间没有重叠，直接将当前区间添加到result中。

返回结果：遍历完成后，result中存储的就是所有合并后的区间，返回这个数组。

复杂度：时间复杂度O(nlogn)，空间复杂度O(n)
过程：

首先定义了Interval类，增加了一个重载的输出流运算符，使得可以方便地打印区间。

然后定义了Solution类，其中包含了merge函数，用于合并区间。

在main函数中，创建了Solution类的实例，并提供了几个测试用例。每个测试用例都打印出合并后的区间。

c++ demo：

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

class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}

    // 重载输出流运算符，以便打印区间
    friend std::ostream& operator<<(std::ostream& os, const Interval& interval) {
        os << "[" << interval.start << ", " << interval.end << "]";
        return os;
    }
};

class Solution {
public:
    std::vector<Interval> merge(std::vector<Interval>& intervals) {
        std::vector<Interval> result;
        if (intervals.empty()) return result;

        // 首先按照区间的开始时间进行排序
        std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
            });

        // 合并区间
        result.push_back(intervals[0]);
        for (const auto& interval : intervals) {
            if (interval.start <= result.back().end) {
                result.back().end = std::max(result.back().end, interval.end);
            }
            else {
                result.push_back(interval);
            }
        }
        return result;
    }
};

// 主函数，用于测试合并区间的算法
int main() {
    Solution solution;
    // 测试用例1
    std::vector<Interval> intervals1 = { {1, 3}, {2, 6}, {8, 10}, {15, 18} };
    std::vector<Interval> merged1 = solution.merge(intervals1);
    std::cout << "Merged intervals: ";
    for (const auto& interval : merged1) {
        std::cout << interval << " ";
    }
    std::cout << std::endl;

    // 测试用例2
    std::vector<Interval> intervals2 = { {1, 4}, {4, 5} };
    std::vector<Interval> merged2 = solution.merge(intervals2);
    std::cout << "Merged intervals: ";
    for (const auto& interval : merged2) {
        std::cout << interval << " ";
    }
    std::cout << std::endl;

    // 测试用例3
    std::vector<Interval> intervals3 = { {1, 100} };
    std::vector<Interval> merged3 = solution.merge(intervals3);
    std::cout << "Merged intervals: ";
    for (const auto& interval : merged3) {
        std::cout << interval << " ";
    }
    std::cout << std::endl;

    return 0;
}