【Hot 100 刷题计划】 LeetCode 56. 合并区间 | C++ 排序与贪心算法题解

LeetCode 56. 合并区间 | C 排序与贪心算法题解 题目描述题目级别中等以数组intervals表示若干个区间的集合其中单个区间为intervals[i] [start_i, end_i]。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间。示例输入intervals [[1,3],[2,6],[8,10],[15,18]]输出[[1,6],[8,10],[15,18]]解释区间[1,3]和[2,6]重叠, 将它们合并为[1,6]。 解题思路排序 贪心合并面对这种无序的区间问题第一反应永远是排序。如果我们按照每个区间的左端点从小到大进行排序那么能够合并的区间一定是连续挨在一起的排序之后我们遍历这些区间对于当前正在处理的区间和下一个区间只会有两种情况有重叠或者包含前一个区间的右端点≥\ge≥后一个区间的左端点。操作由于左端点已经排好序了合并后的新左端点不用动。我们只需要把前一个区间的右端点更新为“这两个区间右端点的最大值”即可。例如[1, 4]和[2, 6]合并成[1, 6][1, 5]和[2, 4]合并依然是[1, 5]。无重叠前一个区间的右端点后一个区间的左端点。操作这说明前面的区间已经合并到极限了不可能再和后面的任何区间有交集。我们直接把后面这个新区间作为一个“新的起步区间”加入到结果集中继续往后比较。 C 代码实现 (优雅优化版)classSolution{public:vectorvectorintmerge(vectorvectorintintervals){// 如果区间为空直接返回if(intervals.empty())return{};// 1. 按照区间的左端点从小到大进行排序// C 的 sort 默认就是按照 vector 的第一个元素排序非常方便sort(intervals.begin(),intervals.end());vectorvectorintres;// 2. 先把排序后的第一个区间放入结果集作为初始的“当前合并区间”res.push_back(intervals[0]);// 3. 从第二个区间开始遍历for(inti1;iintervals.size();i){// 获取结果集中最后一个区间的右端点使用引用方便直接原地修改intcurrent_rightres.back()[1];// 获取下一个即将比较的区间的左右端点intnext_leftintervals[i][0];intnext_rightintervals[i][1];// 情况一如果有重叠当前右端点 下一个左端点if(current_rightnext_left){// 将右端点延长为两者的最大值完成合并current_rightmax(current_right,next_right);}// 情况二如果没有重叠else{// 彻底断开将下一个新区间作为独立区间加入结果集res.push_back(intervals[i]);}}returnres;}};