Last Updated on 2022-02-20 by Clay
題目
Given an arrayintervalswhereintervals[i] = [li, ri]represent the interval[li, ri), remove all intervals that are covered by another interval in the list. The interval[a, b)is covered by the interval[c, d)if and only ifc <= aandb <= d. Return the number of remaining intervals.
Example 1:
Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
Example 2:
Input: intervals = [[1,4],[2,3]] Output: 1
Constraints:
1 <= intervals.length <= 1000intervals[i].length == 20 <= li <= ri <= 105- All the given intervals are unique.
題目給定一組陣列輸入，陣列中包含的每個元素都有一個起點值跟終點值，有些元素是會被其他展開更長的元素覆蓋過去。
比方說 [3, 6] 就會被 [2, 8] 覆蓋掉。
我們要計算被覆蓋之後，仍舊剩下多少組元素。
解題思路
如果我們先將陣列中的元素進行排序，那麼就會按照元素中的第一個值由小到大排序。
我們需要紀錄起第一個元素的『起點值』與『終點值』，並將其用來比較下一個元素。
如果下一個元素的『起點值』大於紀錄起來的『起點值』、並且下一個元素的『終點值』也大於紀錄起來的『終點值』，那麼可以判斷下一個元素肯定不會被覆蓋。
之所以也要比較『起點值』，是因為就算排序過後，仍然可能存在著相同『起點值』與『終點值』的元素。
而每次當前元素的『終點值』大於紀錄起來的『終點值』時，我們要使用當前元素的值來更新『起點值』和『終點值』。
這就是排序的好處，我們基本上只要注意每個元素的終點值即可，起點值只要不相同就不會撞到覆蓋值。
複雜度
因為將陣列進行了排序，故時間複雜度為 n * log(n)。
| Time Complexity | O(n*logn) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int removeCoveredIntervals(vector<vector<int>>& intervals) {
// Sort
sort(intervals.begin(), intervals.end());
// Init
int ans = 1;
int startpoint = intervals[0][0];
int endpoint = intervals[0][1];
// Comparison
for (int i=1; i<intervals.size(); ++i) {
if (intervals[i][1] > endpoint) {
if (intervals[i][0] > startpoint) {
++ans;
}
startpoint = intervals[i][0];
endpoint = intervals[i][1];
}
}
return ans;
}
};Python 範例程式碼
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
# Sort
intervals.sort()
# Init
ans = 1
startpoint = intervals[0][0]
endpoint = intervals[0][1]
# Comparison
for i in range(1, len(intervals)):
if (intervals[i][1] > endpoint):
if (intervals[i][0] > startpoint):
ans += 1
startpoint = intervals[i][0]
endpoint = intervals[i][1]
return ans