请选择 进入手机版 | 继续访问电脑版

LeetCode C++ 435. Non-overlapping Intervals【贪心/排序/动态规划】中等

[复制链接]
卓小兔 发表于 2021-1-1 18:31:45 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
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:
  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:
  1. 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:
  1. 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.
题意:给出一个区间聚集,移除最少数量的区间,使得剩余区间不重合。
  解法 贪心

本题等同于——最多生存多少个区间,让它们之间互相不重叠。关键是按照区间右端点从小到大来进行排序。详细代码如下:
  1. 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;    }};
复制代码
运行效率如下:
  1. 执行用时:32 ms, 在所有 C++ 提交中击败了69.63% 的用户内存消耗:9.3 MB, 在所有 C++ 提交中击败了78.73% 的用户
复制代码
来源:https://blog.csdn.net/myRealization/article/details/108270626
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )