Non-overlapping Intervals

Problem Statement

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

Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.

Example 1:

# Example provided was Java, changed to Python.
intervals = [[1,2],[2,4],[1,4]]
# Expected Output: 1

Explanation: After [1,4] is removed, the rest of the intervals are non-overlapping.

Example 2:

# Example provided was Java, changed to Python.
intervals = [[1,2],[2,4]]
# Expected Output: 0

Constraints:

  • 1 <= len(intervals) <= 1000
  • len(intervals[i]) == 2
  • -50000 <= start_i < end_i <= 50000

Aim for a solution with O(n log n) time complexity due to sorting and O(1) or O(n) space complexity, depending on the sorting algorithm.

Hint 1

Think about sorting the intervals based on some criteria (e.g., start time or end time).

Hint 2

Greedy approaches are often effective for interval scheduling problems. Consider selecting intervals that minimize overlap with subsequent intervals.

Hint 3

Dynamic programming can be used, but is often less efficient than greedy algorithms for this problem.

Solution

Recursion

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort()


    def dfs(i, prev):
        if i == len(intervals):
            return 0
        res = dfs(i + 1, prev)
        if prev == -1 or intervals[prev][1] <= intervals[i][0]:
            res = max(res, 1 + dfs(i + 1, i))
        return res


    return len(intervals) - dfs(0, -1)

Time complexity: O(2 ^ n) Space complexity: O(n)

Dynamic Programming (Top-Down)

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key = lambda x: x[1])
    n = len(intervals)
    memo = {}


    def dfs(i):
        if i in memo:
            return memo[i]


        res = 1
        for j in range(i + 1, n):
            if intervals[i][1] <= intervals[j][0]:
                res = max(res, 1 + dfs(j))
        memo[i] = res
        return res


    return n - dfs(0)

Time complexity: O(n ^ 2) Space complexity: O(n)

Dynamic Programming (Bottom-Up)

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    dp = [0] * n


    for i in range(n):
        dp[i] = 1
        for j in range(i):
            if intervals[j][1] <= intervals[i][0]:
                dp[i] = max(dp[i], 1 + dp[j])


    max_non_overlapping = max(dp)
    return n - max_non_overlapping

Time complexity: O(n ^ 2) Space complexity: O(n)

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    dp = [0] * n
    dp[0] = 1


    def bs(r, target):
        l = 0
        while l < r:
            m = (l + r) >> 1
            if intervals[m][1] <= target:
                l = m + 1
            else:
                r = m
        return l


    for i in range(1, n):
        idx = bs(i, intervals[i][0])
        if idx == 0:
            dp[i] = dp[i - 1]
        else:
            dp[i] = max(dp[i - 1], 1 + dp[idx - 1])
    return n - dp[n - 1]

Time complexity: O(n log n) Space complexity: O(n)

Greedy (Sort By Start)

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort()
    res = 0
    prev_end = intervals[0][1]


    for start, end in intervals[1:]:
        if start >= prev_end:
            prev_end = end
        else:
            res += 1
            prev_end = min(end, prev_end)
    return res

Time complexity: O(n log n) Space complexity: O(1) or O(n) depending on the sorting algorithm.

Greedy (Sort By End)

def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key = lambda pair: pair[1])
    prev_end = intervals[0][1]
    res = 0


    for i in range(1, len(intervals)):
        if prev_end > intervals[i][0]:
            res += 1
        else:
            prev_end = intervals[i][1]


    return res

Time complexity: O(n log n) Space complexity: O(1) or O(n) depending on the sorting algorithm.