Non-overlapping Intervals - LeetCode

給一個array，裡面放很多個 [開始 結束] 的array

把重疊的踢掉，剩下的都要是不重疊的，回傳最小的剔除次數

• Examples

May 25, 2024

"""
= after sorted by start =

overlap case 1:
s--e
  s-----e x
           s--e

overlap case 2:
s------e  x
  s--e 
           s--e
"""

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 1:
            return 0

        def is_overlap(interval1, interval2):
            if interval1[1] > interval2[0]:
                return True
            return False

        count = 0
        sorted_intervals = sorted(intervals, key=lambda x:x[0])

        prev = sorted_intervals[0]

        for i in range(1, len(sorted_intervals)):
            itv = sorted_intervals[i]
            if is_overlap(prev, itv):
                count += 1
                # if case2, update prev
                if prev[1] >= itv[1]: 
                    prev = itv
            else:
                prev = itv

        return count

December 27, 2023

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        prev_end = sorted_intervals[0][1]
        count = 0
        
        for i in range(1, len(sorted_intervals)):
            interval = sorted_intervals[i]
            # 若當前的頭比上一條的尾巴還小，必須拿掉其中一條
            # 拿掉兩條中，尾巴較大的那條，才能讓 count 最小
            if interval[0] < prev_end:
                count += 1
                prev_end = min(prev_end, interval[1])
            else:
                prev_end = interval[1]
        
        return count

Time: O(n log n) for sorting, O(n) for iterating, total is O(n log n)

Space: O(1)

排序

維護一個 prevEnd, 預設值：排序後的第一個的第二個值 intervals.sort[0][1]

維護一個 remove = 0