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
Recommended Time and Space Complexity
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)
Dynamic Programming (Binary Search)
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.