435 Non-overlapping Intervals 無重疊區(qū)間
Description:
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:
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:
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.
題目描述:
給定一個(gè)區(qū)間的集合渗常，找到需要移除區(qū)間的最小數(shù)量苔咪，使剩余區(qū)間互不重疊泰偿。
注意：
可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)休涤。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊盒刚。
示例 :
示例 1:
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后掀淘，剩下的區(qū)間沒有重疊砚亭。
示例 2:
輸入: [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊曾棕。
示例 3:
輸入: [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間扣猫，因?yàn)樗鼈円呀?jīng)是無重疊的了。
思路:
按照區(qū)間的右端點(diǎn)排序, 取第一個(gè)的右端點(diǎn), 如果下一個(gè)端點(diǎn)的左端點(diǎn)在上一個(gè)端點(diǎn)的左邊, 說明要去掉這個(gè)區(qū)間, 否則更新新的右端點(diǎn)
時(shí)間復(fù)雜度O(nlgn), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals)
{
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.back() < b.back(); });
int count = 0, right = intervals[0].back();
for (int i = 1; i < intervals.size(); i++)
{
if (right > intervals[i].front()) ++count;
else right = intervals[i].back();
}
return count;
}
};
Java:
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, new Comparator<int[]>() { public int compare(int[] a, int[] b) { return a[1] - b[1]; } });
int count = 0, right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (right > intervals[i][0]) ++count;
else right = intervals[i][1];
}
return count;
}
}
Python:
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals.sort(key = lambda x : x[1])
count, n, right = 0, len(intervals), intervals[0][1]
for i in range(1, n):
if right > intervals[i][0]:
count += 1
else:
right = intervals[i][1]
return count
