当前位置:首页 > 力扣 > 力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理

2个月前 (07-11)

力扣LCR074题区间合并算法解析:贪心排序与区间重叠处理 贪心算法 C++ 力扣题解 力扣LCR题 数组 第1张

一、题目解读

力扣LCR074题要求对给定的二维区间数组(每个区间由起始点和终止点构成)进行合并,将重叠的区间合并为更宽的区间,最终输出不重叠的合并结果。例如,输入[[1,3],[2,6],[8,10],[15,18]],输出[[1,6],[8,10],[15,18]]。核心在于判断区间重叠逻辑与合并策略。

二、解题思路

采用贪心算法排序结合的思路:

1. 先排序:按区间起始点升序排列,确保后续遍历时能自然判断相邻区间的重叠关系。

2. 再合并:遍历排序后的区间,通过比较当前区间与末尾合并区间的终止点,决定是否合并或新增区间。

该思路关键在于利用排序减少遍历时的决策复杂度,符合贪心策略的“局部最优解推动全局最优”原则。

三、解题步骤

1. 空数组处理:若输入为空,直接返回空数组,避免后续逻辑错误。

2. 排序区间:使用C++的sort函数配合自定义比较函数(lambda表达式),按区间起始点排序。

3. 初始化合并数组:将第一个区间加入merged数组,作为合并基准。

4. 遍历合并:

○ 从第2个区间开始遍历,每次获取merged末尾区间(last)。

○ 若当前区间起始点≤ last[1](即重叠),则更新last[1]为二者终止点的最大值。

○ 若不重叠,直接添加当前区间至merged。

5. 返回结果:最终merged即为合并后的不重叠区间列表。

四、代码与注释

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
    
    // 1. 按照区间起始点排序
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    
    // 2. 遍历并合并重叠区间
    for (int i = 1; i < intervals.size(); ++i) {
        // 获取最后一个合并后的区间
        vector<int>& last = merged.back();
        
        // 如果当前区间与最后一个合并区间重叠
        if (intervals[i][0] <= last[1]) {
            // 合并区间,取最大的结束点
            last[1] = max(last[1], intervals[i][1]);
        } else {
            // 不重叠,直接添加新区间
            merged.push_back(intervals[i]);
        }
    }
    
    return merged;
    }
};

五、总结

该解法时间复杂度为O(nlogn)(排序)+ O(n)(遍历),空间复杂度为O(n)(合并数组)。优点是逻辑简洁、易于实现,缺点是对大规模数据排序可能耗时。实际应用中,若区间数量可控,此贪心排序策略能有效解决重叠合并问题。建议进一步优化可探索不排序的区间或扫描线算法,但复杂度可能上升。


原创内容 转载请注明出处

分享给朋友:

相关文章

【深度优先搜索实战】力扣547题:省份数量问题的图论解法

【深度优先搜索实战】力扣547题:省份数量问题的图论解法

题目解读‌我们面对的是一个典型的图论问题:给定一个城市的连接矩阵,需要计算其中相互连通的城市群(省份)数量。这个问题可以抽象为无向图中的连通分量计算,每个城市代表图中的一个节点,城市之间的连接关系代表...

力扣145:递归之美 轻松掌握二叉树后序遍历

力扣145:递归之美 轻松掌握二叉树后序遍历

题目解读二叉树的后序遍历是一种基础且重要的树遍历方式,其遍历顺序为:先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。这种遍历方式特别适合需要先处理子节点再处理父节点的场景,如内存释放...

力扣94:递归之美 轻松掌握二叉树中序遍历

力扣94:递归之美 轻松掌握二叉树中序遍历

题目解读二叉树的中序遍历是一种基础且重要的树遍历方式,其遍历顺序为:先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。对于二叉搜索树,中序遍历的结果恰好是节点值的升序排列。给定一个二叉...

手搓顺序表类代码注释与详解:从零实现动态数组(新手教程)

一、简介和特点顺序表(Sequential List)是数据结构中基础的一种线性表,其特点是将数据元素存储在连续的内存空间中。通过数组实现,支持随机访问(即通过索引直接访问元素),适用于频繁随机读取的...

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

牛客13271题「删除K个数字的最小数」解题报告:贪心算法与栈的应用(附代码注释)

一、题目解读牛客13271题要求从给定的数字字符串中删除K个数字,使得剩余数字按原顺序排列后得到的最小数。题目核心在于如何在保持数字相对顺序的前提下,通过删除操作得到最优解。需注意结果字符串可能包含前...

【力扣3115题解】数组中质数最大差值的求解(C++代码详解)

【力扣3115题解】数组中质数最大差值的求解(C++代码详解)

一、题目解读力扣3115题要求在一个整数数组中,找出两个质数之间的最大差值。若数组不存在质数,则返回0。题目核心在于高效筛选质数,并计算其索引差值的最大值,需兼顾时间与空间复杂度。二、解题思路参考代码...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。