SHARE
TWEET

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!
  1. 用 interval.end 排序, 贪婪法.
  2. O(n log n) time
  3.  
  4. from leetcode discuss: A classic greedy case: interval scheduling problem.
  5.  
  6. 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).
  7. The reason is, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
  8.  
  9. 数据结构:
  10. pre_start, pre_end = intervals[0] 记录尾区间的起止位置.
  11. 遍历每一个 interval,
  12. - start,end = intervals[i]
  13. - if start < pre_end: continue # 有重叠, 跳过一个, 计数加一, 继续,
  14. - else: ans += 1, pre_end = end # 没有重叠, 加进一个新区间, 更新尾区间结束位置.
  15. .
  16.  
  17. class Solution:
  18.     def eraseOverlapIntervals(self, intervals):
  19.         A = intervals
  20.         if not A:
  21.             return 0
  22.         A.sort(key = lambda x:(x[1], x[0]))
  23.         pre_end = A[0][1]
  24.         n = len(A)
  25.         ans = 0
  26.        
  27.         for i in range(1, n):
  28.             start, end = A[i]
  29.             if start < pre_end:
  30.                 ans += 1
  31.             else:
  32.                 pre_end = end
  33.         return ans
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top