[LeetCode] 435. Non-overlapping Intervals 非重叠区间
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals 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.
Example 1:
Input: [ [1,2], [2,3], [3,4], [1,3] ] Output: 1 Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
Example 2:
Input: [ [1,2], [1,2], [1,2] ] Output: 2 Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
Example 3:
Input: [ [1,2], [2,3] ] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
这道题给了我们一堆区间,让求需要至少移除多少个区间才能使剩下的区间没有重叠,那么首先要给区间排序,根据每个区间的 start 来做升序排序,然后开始要查找重叠区间,判断方法是看如果前一个区间的 end 大于后一个区间的 start,那么一定是重复区间,此时结果 res 自增1,我们需要删除一个,那么此时究竟该删哪一个呢,为了保证总体去掉的区间数最小,我们去掉那个 end 值较大的区间,而在代码中,我们并没有真正的删掉某一个区间,而是用一个变量 last 指向上一个需要比较的区间,我们将 last 指向 end 值较小的那个区间;如果两个区间没有重叠,那么此时 last 指向当前区间,继续进行下一次遍历,参见代码如下:
解法一:
class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { int res = 0, n = intervals.size(), last = 0; sort(intervals.begin(), intervals.end()); for (int i = 1; i < n; ++i) { if (intervals[i][0] < intervals[last][1]) { ++res; if (intervals[i][1] < intervals[last][1]) last = i; } else { last = i; } } return res; } };
我们也可以对上面代码进行简化,主要利用三元操作符来代替 if 从句,参见代码如下:
解法二:
class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { if (intervals.empty()) return 0; sort(intervals.begin(), intervals.end()); int res = 0, n = intervals.size(), endLast = intervals[0][1]; for (int i = 1; i < n; ++i) { int t = endLast > intervals[i][0] ? 1 : 0; endLast = t == 1 ? min(endLast, intervals[i][1]) : intervals[i][1]; res += t; } return res; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/435
类似题目:
Data Stream as Disjoint Intervals
Minimum Number of Arrows to Burst Balloons
参考资料:
https://leetcode.com/problems/non-overlapping-intervals/
https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java%3A-Least-is-Most
https://leetcode.com/problems/non-overlapping-intervals/discuss/91700/Concise-C%2B%2B-Solution
相关文章
- Leetcode: 24 Game
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- LeetCode高频题56. 合并区间,将重叠的区间合并为一个区间,包含所有区间
- [LeetCode]1029. 两地调度
- LeetCode 435. 无重叠区间
- 140、【贪心算法】leetcode ——763. 划分字母区间(区间边界更新)(C++版本)
- 138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
- leetcode竞赛记录-第63场周赛
- LeetCode--N-Queens
- leetcode || 58、Length of Last Word
- 【LeetCode-面试算法经典-Java实现】【056-Merge Intervals(区间合并)】
- LeetCode:Balanced Binary Tree
- [LeetCode] 1046. Last Stone Weight 最后的石头重量
- [LeetCode] 1041. Robot Bounded In Circle 困于圆圈路径中的机器人
- [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和
- [LeetCode] 910. Smallest Range II 最小区间之二
- [LeetCode] 908. Smallest Range I 最小区间
- [LeetCode] 995. Minimum Number of K Consecutive Bit Flips 连续K位翻转的最小次数
- [LeetCode] Construct Quad Tree 建立四叉树
- [LeetCode] 631. Design Excel Sum Formula 设计Excel表格求和公式
- [LeetCode] Split Array with Equal Sum 分割数组成和相同的子数组
- [LeetCode] Palindrome Pairs 回文对
- [LeetCode] Expression Add Operators 表达式增加操作符
- [LeetCode] 41. First Missing Positive 首个缺失的正数
- [LeetCode] 56. Merge Intervals 合并区间
- leetcode 560. Subarray Sum Equals K 和为 K 的子数组(中等)