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.