Leetcode 435. Non-overlapping Intervals

📅2023-07-19🧐73

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

I think this question is similar with 1751. Maximum Number of Events That Can Be Attended II , we could use dynamic programming to solve it in O(n log n) time complexity.

First we need to sort the input list. Then use dp top-down solution to find the answer

from bisect import bisect_left

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

        intervals.sort(key=lambda x: x[0])
        starts = [x for x, _ in intervals]

        @lru_cache(maxsize=None)
        def dp(i):
            if i == len(intervals):
                return 0

            left = bisect_left(starts, intervals[i][1])
            take = 1 + dp(left)
            drop = dp(i + 1)

            return max(take, drop)

        return len(intervals) - dp(0)

But, we could use greedy solve it in O(n log n) time complexity. even the time looks the same, greedy mainly takes O(n log n) on the sort algorithm, in the loop just takes O (n), in the contrast, DP solution takes O(n log n) on the sort first, then take O(n) + O (n log n) in the loop. so greedy is better than DP here.

Another important thing is if we use greedy, mainly we focus on the previous end time, so we need to sort by end not the start

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

        intervals.sort(key=lambda x: x[1])
        
        count, prev_end = 0, -float('inf')

        for start, end in intervals:
            if start < prev_end:
                count += 1
            else:
                prev_end = end

        return count