435. Non-overlapping Intervals
goodwish Oct 21st, 2019 65 in 338 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- 用 interval.end 排序, 贪婪法.
- O(n log n) time
- from leetcode discuss: A classic greedy case: interval scheduling problem.
- The heuristic is: always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals. (or minimal number to remove).
- The reason is, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
- pre_start, pre_end = intervals 记录尾区间的起止位置.
- 遍历每一个 interval,
- - start,end = intervals[i]
- - if start < pre_end: continue # 有重叠, 跳过一个, 计数加一, 继续,
- - else: ans += 1, pre_end = end # 没有重叠, 加进一个新区间, 更新尾区间结束位置.
- class Solution:
- def eraseOverlapIntervals(self, intervals):
- A = intervals
- if not A:
- return 0
- A.sort(key = lambda x:(x, x))
- pre_end = A
- n = len(A)
- ans = 0
- for i in range(1, n):
- start, end = A[i]
- if start < pre_end:
- ans += 1
- pre_end = end
- return ans
RAW Paste Data