Non-overlapping Intervals
Non-overlapping Intervals is a medium intervals problem solved with the basics pattern.
The best approach, optimal (greedy by earliest end), runs in O(n log n) time and O(log n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (sort by start + longest chain dp) up.
Problem
You are given an array of intervals where intervals[i] = [start, end]. Return the minimum number of intervals you must remove so that the remaining intervals do not overlap each other.
Two intervals that only touch at an endpoint, such as [1, 2] and [2, 3], are not considered overlapping.
Examples
Example 1
- Input
intervals = [[2, 5], [1, 3], [4, 7], [6, 8]]- Output
2- Why
- Keeping [1, 3] and [4, 7] (or [1, 3] and [6, 8]) leaves no overlaps; at most two intervals can stay, so two must go.
Example 2
- Input
intervals = [[1, 2], [2, 3], [3, 4]]- Output
0- Why
- Intervals that only touch at an endpoint do not overlap.
Example 3
- Input
intervals = [[0, 10], [1, 2], [3, 4], [5, 6]]- Output
1- Why
- Removing the long interval [0, 10] is enough; the three short ones are disjoint.
Constraints
1 <= intervals.length <= 10^5intervals[i].length == 2-5 * 10^4 <= start < end <= 5 * 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (sort by start + longest chain DP) | O(n²) | O(n) |
| Optimal (greedy by earliest end) | O(n log n) | O(log n) |
1Brute force (sort by start + longest chain DP)
O(n²)Each interval looks back at every earlier interval.O(n)The dp array.Sort by start. Let dp[i] be the largest number of non-overlapping intervals that can be kept with interval i as the last one. It is 1 plus the best dp[j] over earlier intervals j that end at or before start[i]. The answer is n minus the largest dp value.
- Sort intervals by start.
- dp[i] = 1 + max(dp[j]) over j < i with end[j] <= start[i] (or 1 if none).
- Return n - max(dp).
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int n = intervals.length;
int[][] a = intervals.clone();
Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
int[] dp = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j][1] <= a[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return n - best;
}
}class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
n = len(intervals)
a = sorted(intervals, key=lambda x: x[0])
dp = [1] * n
for i in range(n):
for j in range(i):
if a[j][1] <= a[i][0] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
return n - max(dp)class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<vector<int>> a = intervals;
sort(a.begin(), a.end(), [](const vector<int>& x, const vector<int>& y) { return x[0] < y[0]; });
vector<int> dp(n, 1);
int best = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j][1] <= a[i][0]) dp[i] = max(dp[i], dp[j] + 1);
}
best = max(best, dp[i]);
}
return n - best;
}
};function eraseOverlapIntervals(intervals) {
const n = intervals.length;
const a = [...intervals].sort((x, y) => x[0] - y[0]);
const dp = new Array(n).fill(1);
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (a[j][1] <= a[i][0]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
best = Math.max(best, dp[i]);
}
return n - best;
}2Optimal (greedy by earliest end)
O(n log n)Sorting dominates; the sweep is linear.O(log n)Only the sort's own stack (the sweep uses two variables).Among all intervals that could come next, keeping the one that ends first never hurts: it leaves the most room for the rest. So sort by end, sweep once, keep an interval if it starts at or after the end of the last kept one, and count every other interval as removed.
- Sort intervals by end.
- lastEnd = end of the first interval, kept = 1.
- For each next interval: if start >= lastEnd, keep it (kept++, lastEnd = its end); otherwise it is removed.
- Return n - kept.
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> Integer.compare(x[1], y[1]));
int kept = 1;
int lastEnd = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= lastEnd) {
kept++;
lastEnd = intervals[i][1];
}
}
return intervals.length - kept;
}
}class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
kept = 1
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end:
kept += 1
last_end = end
return len(intervals) - keptclass Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& x, const vector<int>& y) { return x[1] < y[1]; });
int kept = 1;
int lastEnd = intervals[0][1];
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= lastEnd) {
kept++;
lastEnd = intervals[i][1];
}
}
return intervals.size() - kept;
}
};function eraseOverlapIntervals(intervals) {
intervals.sort((x, y) => x[1] - y[1]);
let kept = 1;
let lastEnd = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= lastEnd) {
kept++;
lastEnd = intervals[i][1];
}
}
return intervals.length - kept;
}Edge cases to test
- A single interval (answer 0)
- Intervals that only share an endpoint (not an overlap)
- Duplicate intervals
- One long interval covering many short ones: remove the long one, not the short ones
- Negative coordinates
Hints
Hint 1
Removing as few intervals as possible is the same as keeping as many pairwise non-overlapping intervals as possible.
Hint 2
Which interval is the safest to keep first? The one that frees up the timeline the earliest.
Hint 3
Sort by end point. Keep an interval whenever its start is at or after the end of the last kept interval; count the rest as removed.
FAQ
What is the best time complexity for Non-overlapping Intervals?
Optimal (greedy by earliest end) runs in O(n log n) time and O(log n) extra space. Sorting dominates; the sweep is linear.
Which pattern does Non-overlapping Intervals use?
It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.
Is there a brute force solution for Non-overlapping Intervals?
Yes. Brute force (sort by start + longest chain DP) takes O(n²) time and O(n) space. Sort by start.
Which edge cases should I test for Non-overlapping Intervals?
A single interval (answer 0); Intervals that only share an endpoint (not an overlap); Duplicate intervals; One long interval covering many short ones: remove the long one, not the short ones; Negative coordinates.