LeetCode C++ 435. Non-overlapping Intervals【贪心/排序/动态规划】中等
发布日期:2021-07-01 02:50:29
浏览次数:4
分类:技术文章
本文共 1531 字,大约阅读时间需要 5 分钟。
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Example 1:
Input: [[1,2],[2,3],[3,4],[1,3]]Output: 1Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [[1,2],[1,2],[1,2]]Output: 2Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [[1,2],[2,3]]Output: 0Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Note:
- You may assume the interval’s end point is always bigger than its start point.
- Intervals like
[1,2]
and[2,3]
have borders “touching” but they don’t overlap each other.
题意:给出一个区间集合,移除最少数量的区间,使得剩余区间不重合。
解法 贪心
本题等同于——最多保留多少个区间,让它们之间互相不重叠。关键是按照区间右端点从小到大来进行排序。具体代码如下:
class Solution { public: int eraseOverlapIntervals(vector>& intervals) { if (intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), [&](const vector &a, const vector &b) { return a[1] != b[1] ? a[1] < b[1] : a[0] < b[0]; }); int nonOverlapping = 0, n = intervals.size(), end = INT_MIN; for (int i = 0; i < n; ++i) { if (intervals[i][0] >= end) { ++nonOverlapping; end = intervals[i][1]; } } return n - nonOverlapping; }};
运行效率如下:
执行用时:32 ms, 在所有 C++ 提交中击败了69.63% 的用户内存消耗:9.3 MB, 在所有 C++ 提交中击败了78.73% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108270626 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月29日 11时07分22秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java对象深复制、浅复制
2019-05-03
JVM之垃圾回收
2019-05-03
Java 对象初始化过程
2019-05-03
细分自动化测试
2019-05-03
Selenium RC
2019-05-03
Java中List与数组的转换
2019-05-03
使用WebDriver完成web页面切换操作(附源码)
2019-05-03
WebDriver自定义显示等待条件
2019-05-03
在eclipse中显示GC情况
2019-05-03
webDriver自定义浏览器打开的等待时间
2019-05-03
webDriver中的几种timeout
2019-05-03
使用webdriver中的JavascriptExecutor执行js改变DOM属性
2019-05-03
WebDriver中close()与quit()的不同
2019-05-03
解决webdriver(Element not found in the cache - perhaps the page has changed since it was looked up )
2019-05-03
LR 杂记--loadrunner录制回放常见问题总结
2019-05-03
tcp 高性能服务, netty,mqtt
2019-05-03
排期模板
2019-05-03
物联网安全设计
2019-05-03
调研 中央空调 地暖 水暖
2019-05-03