Leetcode # 435. Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals

First Solution

Time Complexity: O(len(intervals))
Space Complexity: O(len(intervals))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    starts = collections.defaultdict(list)
    for i in intervals:
      starts[i[0]].append(i[1])
    removed_n = sum([len(starts[s]) - 1 for s in starts])
    left_intervals = sorted([[s, min(starts[s])]for s in starts])
    i = 0
    while i < len(left_intervals) - 1:
      if left_intervals[i][1] > left_intervals[i + 1][0]:
        if left_intervals[i][1] >= left_intervals[i + 1][1]:
          left_intervals.pop(i)
        else:
          left_intervals.pop(i + 1)
        removed_n += 1
      else:
        i += 1
    
    return removed_n

Refined Solution

第一版的演算法主要有兩個部分

1. if start_i == start_j and end_i <= end_j
   ⇒ 刪除 intervals[j]
2. if start_i > end_j ⇒ 刪除 intervals[argmax_{k=i, j}(end_k)]

可以總結為：
if intervals[i] and intervals[j] overlapped
⇒ 刪除 intervals[argmax_{k=i, j}(end_k)]

Time Complexity: O(len(intervals))
Space Complexity: O(len(intervals))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    _intervals = sorted(intervals, key = lambda x:x[1])
    removed_n = 0
    previous_end = -inf
    for s, e in _intervals:
      if s >= previous_end:
        previous_end = e
      else:
        removed_n += 1
    return removed_n

Last Updated on 2023/08/16 by A1go