https://leetcode.com/problems/non-overlapping-intervals/submissions/
435. Non-overlapping Intervals
Given an array of intervals intervals where intervals[i] = [starti, endi],
return the minimum number of intervals you need to remove to make the rest of
the intervals non-overlapping.
給一堆區間 要你算刪掉幾個區間會讓他們不重疊
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-
overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals
non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're
already non-overlapping.
Step：
0. Vec.len() = 0 判斷
1. 先根據區間尾排列Vec
2. 設result = 1代表不重複區間數，設last_tail來當目前區間的尾
3. 前後區間不重疊(後者head >= 前者tail)則result+1
4. return 區間數減不重複區間數
只算重疊區間也可以 就反過來寫
Code:
impl Solution
{
pub fn erase_overlap_intervals(intervals: Vec<Vec<i32>>) -> i32
{
if intervals.is_empty()
{
return 0;
}
let mut intervals = intervals;
intervals.sort_by(|a, b| a[1].cmp(&b[1]));
let mut result = 1;
let mut last_tail = intervals[0][1];
for pair_nums in intervals.iter()
{
if(pair_nums[0] >= last_tail)
{
last_tail = pair_nums[1];
result += 1;
}
}
return (intervals.len() - result) as i32;
}
}
等價於：
class Solution
{
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
if (intervals.size() < 1)
return 0;
std::sort(intervals.begin(), intervals.end(),
[](vector<int>& a, vector<int>& b)
{
return a[1] < b[1];
});
int result = 0;
int last_tail = intervals[0][1];
for (auto& pair_nums : intervals)
{
if (pair_nums[0] >= last_tail)
{
last_tail = pair_nums[1];
result++;
}
}
return intervals.size() - result;
}
};