当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(55)聚宝盆装区间 - 合并区间(排序贪心)

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(55)聚宝盆装区间 - 合并区间(排序贪心)

哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的聚宝盆谷,谷中有一只巨大的聚宝盆,盆身闪烁着神秘的光芒。谷口有一块巨大的石碑,上面刻着一行文字:“欲装此盆,需以聚宝之力,合并区间,排序贪心显真身。”

哪吒定睛一看,石碑上还有一行小字:“区间[[1,3],[2,6],[8,10],[15,18]]合并后为[[1,6],[8,10],[15,18]]。”哪吒心中一动,他知道这是一道关于合并区间的难题,需要通过排序和贪心策略来解决。

暴力解法:聚宝盆的初次尝试

哪吒心想:“要合并区间,我可以逐个区间检查。”他催动聚宝盆之力,通过逐个区间比较,试图找到重叠或相邻的区间并合并。

vector<vector<int>> merge(vector<vector<int>>& intervals) {
   
    vector<vector<int>> result;
    if (intervals.empty()) return result;
    sort(intervals.begin(), intervals.end());
    vector<int> current = intervals[0];
    for (int i = 1; i < intervals.size(); ++i) {
   
        if (intervals[i][0] <= current[1]) {
   
            current[1] = max(current[1], intervals[i][1]);
        } else {
   
            result.push_back(current);
            current = intervals[i];
        }
    }
    result.push_back(current);
    return result;
}

哪吒成功地合并了区间,但聚宝盆的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当区间数量很多时,灵力消耗巨大。

C++语法点

在C++中,合并区间问题涉及到排序和贪心策略。以下是一些重要特性:

  • 排序

    • 使用sort函数对区间按起始位置排序。
    • 常用操作:
      • sort(intervals.begin(), intervals.end()):按区间起始位置排序。
  • 贪心策略

    • 通过维护当前区间,逐步合并重叠或相邻的区间。

高阶优化:排序贪心的智慧

哪吒元神中突然浮现金色铭文——「聚宝盆装区间,排序贪心显真身」。他意识到,可以通过排序和贪心策略优化区间合并过程。

哪吒决定使用排序和贪心策略,先按区间起始位置排序,然后维护一个当前区间,逐步合并重叠或相邻的区间。通过这种方式,他成功地合并了所有区间,而且灵力消耗大幅减少。

vector<vector<int>> merge

http://www.kler.cn/a/587266.html

相关文章:

  • 【Erdas实验教程】015:哨兵二号卫星数据简介及下载方法
  • PyTorch系列教程:基于LSTM构建情感分析模型
  • Spring Boot应用首次请求性能优化实战:从数据库连接池到JVM调优
  • OSPF | LSDB 链路状态数据库 / SPF 算法 / 实验
  • 爬虫逆向:Hook 技术原理与实战
  • Java 学习记录:基础到进阶之路(二)
  • Mac中nvm切换node版本失败,关闭终端再次打开还是之前的node
  • Rubick:基于 Electron 的开源插件化桌面效率工具箱
  • C++之list类(超详细)
  • Cursor的使用感受,帮你使用好自动化编程工具,整理笔记
  • Unity开发——点击事件/射线检测
  • LeetCode 热题 100_前 K 个高频元素(73_347_中等_C++)(堆)(哈希表+排序;哈希表+优先队列(小根堆))
  • 【机器人】复现 ASGrasp 通用透明物体重建、6-DoF抓取预测
  • 基于VM的CentOS 7.4系统安装与配置说明系统环境主机系统
  • windows,修改svn密码之后,没法认证
  • Gemini 2.0 Flash:AI 图像生成的革命性突破!
  • 数学建模 第一节
  • 2min搞定~Mac Pro 编译安装 Nginx 1.8.1
  • RBAC 模型的简单实现
  • 19、Template