【3.8】贪心算法-解无重叠区间

ops/2025/1/16 5:53:26/

一、题目

        给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

二、解题思路

        要解决这个问题,我们可以使用算法>贪心算法算法>贪心算法的核心思想是在每一步选择中都采取当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的。

对于这个问题,我们可以按照以下步骤进行:

  1. 按照区间的结束时间进行排序:这样可以确保我们优先选择结束时间早的区间,从而给后面的区间留下更多的空间。

  2. 遍历排序后的区间:从第二个区间开始,检查当前区间的开始时间是否与前一个区间的结束时间重叠。如果重叠,则需要移除当前区间(因为我们要尽量保留结束时间早的区间);如果不重叠,则保留当前区间。

  3. 记录移除的区间数量:在遍历过程中,记录需要移除的区间数量。

具体实现步骤如下:

  1. 将区间按照结束时间进行排序。

  2. 初始化一个变量 remove_count 用于记录移除的区间数量,初始化为 0。

  3. 初始化一个变量 prev_end 用于记录前一个区间的结束时间,初始化为第一个区间的结束时间。

  4. 从第二个区间开始遍历,如果当前区间的开始时间小于 prev_end,则说明当前区间与前一个区间重叠,需要移除,remove_count 加 1。

  5. 如果当前区间的开始时间大于或等于 prev_end,则说明当前区间与前一个区间不重叠,更新 prev_end 为当前区间的结束时间。

  6. 遍历结束后,返回 remove_count

三、代码实现

#include <iostream>
#include <vector>
#include <algorithm>// 比较函数,用于排序
bool compareIntervals(const std::vector<int>& a, const std::vector<int>& b) {return a[1] < b[1];
}int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {if (intervals.empty()) {return 0;}// 按照结束时间进行排序std::sort(intervals.begin(), intervals.end(), compareIntervals);int remove_count = 0;int prev_end = intervals[0][1];for (size_t i = 1; i < intervals.size(); ++i) {if (intervals[i][0] < prev_end) {// 当前区间与前一个区间重叠,需要移除++remove_count;} else {// 当前区间与前一个区间不重叠,更新 prev_endprev_end = intervals[i][1];}}return remove_count;
}int main() {std::vector<std::vector<int>> intervals1 = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};std::cout << "Example 1: " << eraseOverlapIntervals(intervals1) << std::endl; // 输出: 1return 0;
}


http://www.ppmy.cn/ops/105405.html

相关文章

UI自动化-元素动作WebElement源码类

UI自动化设计元素动作所用到的源码是WebElement源码类 其中用的最多的为前9个&#xff0c;后续是前端开发时常用 webelement源码类 元素动作都是webelement源码类中 1、往输入框里输入内容&#xff0c;元素单击后输入内容&#xff1a;key的值是要查找的值 获取标签的名称 tagn…

【FPGA】入门学习路线

文章目录 编程语言语法RTL设计RTL验证学习方法仿真工具 基础知识&#xff08;1&#xff09;专业基础课&#xff08;2&#xff09;FPGA相关专业知识&#xff08;3&#xff09;FPGA开发流程 开发工具动手实验 编程语言 硬件描述语言HDL&#xff08;Hardware Description Languag…

【Xcode】Xcode基本使用指引

文章目录 Xcode安装及iphone模拟器的安装Xcode中Debug和Release的切换Xcode中控件的使用Xcode工程的基本组成Xcode UI基本设计及使用iOS开发项目中的日志系统静态库支持多种架构制作xcframeworklibuv库Xcode路径.pbxproj文件苹果平台的宏Leaks检测内存泄漏OC中的ARC和MRC小结 X…

在线音乐播放器项目

在线音乐播放器项目 登录页面 注册页面 主页 上传文件 我的喜欢 前端 js html css 三剑客 后端 Spring Boot框架 插件有:Spring Boot DevTools、Lombok、Spring Web、MySQL Driver、MyBatis Framework、security、detect 数据库有 三张表 lovemusic、music、user 工具类( co…

Vue 全局数据:提升开发效率的利器

在 Vue 开发中&#xff0c;全局数据的管理是一个非常重要的环节。合理地使用全局数据可以极大地提高开发效率&#xff0c;增强代码的可维护性和可扩展性。本文将深入探讨 Vue 中的全局数据&#xff0c;包括其定义、使用方法以及优势。 一、什么是 Vue 全局数据 在 Vue 应用中&a…

windows C++ 并行编程-并发和UWP(三)

控制执行线程 Windows 运行时使用 COM 线程模型。 在此模型中&#xff0c;根据对象处理其同步的方式&#xff0c;对象被托管在不同的单元中。 线程安全对象托管在多线程单元 (MTA) 中。 必须通过单个线程访问的对象托管在单线程单元 (STA) 中。 在具有 UI 的应用程序中&#…

每天学习一个基础算法之二分查找

目录 前言&#xff1a; 1、对二分查找概念的诠释 2、二分查找的使用场景 3、对比顺序查找与二分查找时间复杂度 4、二分查找的实现代码 代码主体&#xff08;以接口函数的形式&#xff09; 实现思路&#xff1a; 测试部分&#xff08;主函数调用&#xff09; 调试结果 前言&…

【算法每日一练及解题思路】判断字符串是否包含数字

【算法每日一练及解题思路】判断字符串是否含数字 一、题目&#xff1a;给定一个字符串&#xff0c;找出其中不含重复字符的最长子串的长度 二、举例&#xff1a; 比如"abcdefgh",不含数字&#xff1b;比如"1",含数字&#xff1b;比如"a1s",含…