Non-overlapping Intervals
Minimizing Interval Removals to Ensure Non-Overlapping Intervals
In problems involving intervals, it’s important to efficiently manage and handle cases where intervals might overlap.
In this article, we’ll look at a problem where the goal is to determine the minimum number of intervals that need to be removed to ensure that the remaining intervals are non-overlapping.
Problem Description
You are given a list of intervals, where each interval is represented by a pair of integers [start, end]. Your task is to find the minimum number of intervals that need to be removed in order to make the remaining intervals non-overlapping.
Key Definitions:
- Non-overlapping intervals: Two intervals [a, b] and [c, d] are non-overlapping if either:
- b≤c (the first interval ends before the second starts), or
- d≤a (the second interval ends before the first starts).
- Overlapping intervals: Two intervals are overlapping if they share at least one common point. For example:
- [1, 2] and [2, 3] are non-overlapping, because they only meet at point 2.
- [2, 4] and [2, 4] are overlapping, because they share the range [2, 3].
Example 1
Input: intervals = [[1,2],[2,4],[1,4]]
Output: 1
Explanation:
After [1,4] is removed, the rest of the intervals are non-overlapping.
Example 2
Input: intervals = [[1,2],[2,4]]
Output: 0]
Explanation:
- [1,2] and [2,3] overlap, so they are merged into [1,3].
Approach to Solve the Problem
To solve this problem efficiently, we can use a greedy approach. The core idea is to always choose intervals that allow the maximum number of subsequent non-overlapping intervals to remain.
Step-by-Step Plan:
Sort the Intervals:
- First, sort the intervals by their
endtime. The reason for this is that choosing intervals that end earlier will leave more room for the subsequent intervals, maximizing the chances of not having overlapping intervals.
- First, sort the intervals by their
Greedy Selection:
- Iterate through the sorted intervals and always choose the interval that doesn’t overlap with the previously selected interval.
- If an interval overlaps with the previous one, increment the removal count, because we can’t keep both intervals. Instead, we should keep the interval with the earliest end time.
Counting the Removals:
- The number of intervals to remove will be equal to the total number of intervals minus the number of intervals that can be kept (non-overlapping).
Algorithm
- Sort the intervals based on their start time.
- Initialize an empty list
mergedto store the result. - Iterate through the sorted intervals:
- If the current interval overlaps with the last merged interval, merge them.
- Otherwise, add the current interval to the result list.
There are mainly three approach to solve this problem –
- Sorting
- Sweep Line Algorithm
- Greedy
1. Recursion
- Time complexity: O(2^n)
- Space complexity: O(n)
Python
C++
Java
JavaScript
Python
class Solution:
def eraseOverlapIntervals(self, 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)
C++
class Solution {
public:
int eraseOverlapIntervals(vector>& intervals) {
sort(intervals.begin(), intervals.end());
return intervals.size() - dfs(intervals, 0, -1);
}
private:
int dfs(const vector>& intervals, int i, int prev) {
if (i == intervals.size()) return 0;
int res = dfs(intervals, i + 1, prev);
if (prev == -1 || intervals[prev][1] <= intervals[i][0]) {
res = max(res, 1 + dfs(intervals, i + 1, i));
}
return res;
}
};
Java
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
return intervals.length - dfs(intervals, 0, -1);
}
private int dfs(int[][] intervals, int i, int prev) {
if (i == intervals.length) return 0;
int res = dfs(intervals, i + 1, prev);
if (prev == -1 || intervals[prev][1] <= intervals[i][0]) {
res = Math.max(res, 1 + dfs(intervals, i + 1, i));
}
return res;
}
}
JavaScript
class Solution {
/**
* @param {number[][]} intervals
* @return {number}
*/
eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const dfs = (i, prev) => {
if (i === intervals.length) return 0;
let res = dfs(i + 1, prev);
if (prev === -1 || intervals[prev][1] <= intervals[i][0]) {
res = Math.max(res, 1 + dfs(i + 1, i));
}
return res;
};
return intervals.length - dfs(0, -1);
}
}
2. Dynamic Programming (Top-Down)
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int eraseOverlapIntervals(vector>& intervals) {
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int n = intervals.size();
vector memo(n, -1);
int maxNonOverlapping = dfs(intervals, 0, memo);
return n - maxNonOverlapping;
}
private:
int dfs(const vector>& intervals, int i, vector& memo) {
if (i >= intervals.size()) return 0;
if (memo[i] != -1) return memo[i];
int res = 1;
for (int j = i + 1; j < intervals.size(); j++) {
if (intervals[i][1] <= intervals[j][0]) {
res = max(res, 1 + dfs(intervals, j, memo));
}
}
memo[i] = res;
return res;
}
};
Java
public class Solution {
private int[] memo;
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int n = intervals.length;
memo = new int[n];
Arrays.fill(memo, -1);
int maxNonOverlapping = dfs(intervals, 0);
return n - maxNonOverlapping;
}
private int dfs(int[][] intervals, int i) {
if (i >= intervals.length) return 0;
if (memo[i] != -1) return memo[i];
int res = 1;
for (int j = i + 1; j < intervals.length; j++) {
if (intervals[i][1] <= intervals[j][0]) {
res = Math.max(res, 1 + dfs(intervals, j));
}
}
memo[i] = res;
return res;
}
}
Python
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
mp = defaultdict(int)
for start, end in intervals:
mp[start] += 1
mp[end] -= 1
res = []
interval = []
have = 0
for i in sorted(mp):
if not interval:
interval.append(i)
have += mp[i]
if have == 0:
interval.append(i)
res.append(interval)
interval = []
return resJavaScript
class Solution {
/**
* @param {number[][]} intervals
* @return {number}
*/
eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
const n = intervals.length;
let memo = new Array(n).fill(-1);
const dfs = (i) => {
if (i >= n) return 0;
if (memo[i] !== -1) return memo[i];
let res = 1;
for (let j = i + 1; j < n; j++) {
if (intervals[i][1] <= intervals[j][0]) {
res = Math.max(res, 1 + dfs(j));
}
}
memo[i] = res;
return res;
};
const maxNonOverlapping = dfs(0);
return n - maxNonOverlapping;
}
}3. Dynamic Programming (Bottom-Up)
- Time complexity: O(n^2)
- Space complexity: O(n)
C++
Java
Python
JavaScript
C++
class Solution {
public:
int eraseOverlapIntervals(vector>& intervals) {
sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
return a[1] < b[1];
});
int n = intervals.size();
vector dp(n, 0);
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = max(dp[i], 1 + dp[j]);
}
}
}
int maxNonOverlapping = *max_element(dp.begin(), dp.end());
return n - maxNonOverlapping;
}
};
Java
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int n = intervals.length;
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
}
int maxNonOverlapping = Arrays.stream(dp).max().getAsInt();
return n - maxNonOverlapping;
}
}
Python
class Solution:
def eraseOverlapIntervals(self, 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_overlappingJavaScript
class Solution:
def eraseOverlapIntervals(self, 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
