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)
过程：

定义了Solution类，其中包含了merge函数，用于合并区间。
先调用sort函数对所以区间排序；
for循环遍历每个区间，比较区间进行合并；

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

c++ demo：

#include <iostream>
#include <vector>
#include <algorithm>class Solution {
public:std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {if (intervals.empty()) return {};// 按照区间的开始位置进行排序std::sort(intervals.begin(), intervals.end());std::vector<std::vector<int>> merged;merged.push_back(intervals[0]);for (const auto& interval : intervals) {// 获取合并后的最后一个区间auto& last = merged.back();if (interval[0] <= last[1]) {// 如果有重叠，合并区间last[1] = std::max(last[1], interval[1]);}else {// 否则，添加新的区间merged.push_back(interval);}}return merged;}
};int main() {Solution solution;// 示例输入std::vector<std::vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10},{15, 18} };// 调用函数并打印结果std::vector<std::vector<int>> mergedIntervals = solution.merge(intervals);for (const auto& interval : mergedIntervals) {std::cout << "[" << interval[0] << ", " << interval[1] << "]" << " ";// << std::endl;}return 0;
}