Problem¶

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

Example 1:

**Input:** intervals = [[1,2],[2,3],[3,4],[1,3|1,2],[2,3],[3,4],[1,3]]
**Output:** 1
**Explanation:** [1,3] can be removed and the rest of the intervals are non-overlapping.

Solve¶

Bottom-up dynamic programming¶

Dynamic problem, which is a lot similar to 2008. Maximum Earnings From Taxi, 1751. Maximum Number of Events That Can Be Attended II, we try to minimize the value of total element you want to remove.

This is bottom-up approach, where we focus on solve and building necessary all lower information first :

• Sort all intervals by end value, this to ensure when we calculate result of a interval [s_i, e_i], we can already get the best result from range [...e_i-1].
• Try to find the best result cacheResult[i] on each step [s_i, e_i], either:
  • Case 1: Remove our current interval, meaning cacheResult[e_i] = cacheResult[e_i-1] +1
  • Case 2: Use our current interval, meaning cacheResult[e_i] = cacheResult[s_i-1] + <total_of_interval_between_s_i_and_e_i>
• To do this, I keeping track of already processed interval in cacheKey array, while cacheResult keeping the best result of our current set interval of cacheKey, adding them key by key.
  • The expression of above Case 1, and Case 2 replace by calculating using index of current processed interval and key value in cacheKey array.
  • bisect_right here is a perform a literal binary searching on already sorted array cacheKey (by default, as we already sort the intervals by end value), which get the closest index where key[closest-1] <= value < key[closest]. Here I need to check some Off by one error to find the exact equivalence.

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

        intervals.sort(key = getEnds)
        cacheResult = []
        cacheKey = []
        for i, (s, e) in enumerate(intervals):
            cacheKey.append(e)
            if i == 0:
                cacheResult[0] = 0
                continue
            closest = bisect_right(cacheKey, s) - 1
            cacheResult.append(cacheResult[i-1] + 1)
            if closest >= 0:
                cacheResult[i] = min(cacheResult[i], cacheResult[closest] + i - closest -1)

        return cacheResult[len(intervals) -1]

Greedy¶

There isn’t a need of caching the result, as all value with the interval with start s_i come before last end e_(i-1) is an overlap and need to be remove. These isn’t any better case at all. So we can remove them, directly increase our result by 1

• Still sort every intervals by end value
• If start s_i overlap last [...last_end], consider we remove this interval, ans = ans + 1, last_end is un-change as we not adding this interval in to result.
• If start s_i not overlap, consider adding this current interval into our result and update the last_end value

Here is provided Answer from Leetcode

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x: x[1])
        ans = 0
        k = -inf

        for x, y in intervals:
            if x >= k:
                # Case 1
                k = y
            else:
                # Case 2
                ans += 1

        return ans