動機
當初想用處理interval的老套路,stack去做,一直gg 直到看解答才發現,原來這麼簡單
Problem
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: 1Explanation: [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: 2Explanation: 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: 0Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
-5 * 104 <= starti < endi <= 5 * 104
Sol
- 如果有overlap就一定會刪一個
- 刪end最大的那一個
class Solution:
def eraseOverlapIntervals(self, ins: List[List[int]]) -> int:
ins.sort(key=lambda x: x[0])
ret = 0
last = 0
for i in range(1,len(ins)):
if ins[i][0] < ins[last][1]:
ret += 1
if ins[i][1] < ins[last][1]:
last = i
else:
last = i
return ret