Non-overlapping Intervals solution and explanation
IBM
Google
TCS
9 more videos on this problem
Non-Overlapping Intervals - Leetcode 435 - PythonNeetCode · 12:53 · 176K views
L8. Non Overlapping Intervals | Greedy Algorithms Playlisttake U forward · 8:46 · 134K views
Non overlapping intervals | Leetcode #435Techdose · 15:29 · 37K views
Non-overlapping Intervals (LeetCode 435) | Visualizing with different scenarios | GreedyNikhil Lohia · 19:04 · 7K views
Non-overlapping Intervals | LeetCode 435 | C++, Java, PythonKnowledge Center · 20:35 · 7K views
Non-overlapping Intervals II Greedy II DP II Binary Search II Leetcode 435Aryan Mittal · 17:36 · 6K views
Non-overlapping Intervals - LeetCode 435 - Python [O(nlogn) Time and O(1) Space!]Deepti Talesra · 8:54 · 5K views
[Java] Leetcode 435. Non-overlapping Intervals [Intervals #3]Eric Programming · 13:04 · 3K views
Leetcode #435 - Non-Overlapping IntervalsAlgoSTEM · 10:23 · 3K views
Leetcode - Non-overlapping Intervals (Python)Timothy H Chang · 6:25 · 2K views
The problem
Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:
Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:
Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
Constraints:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
Approach overview
Problem Overview: You are given a list of intervals where each interval has a start and end time. Some intervals overlap. The goal is to remove the minimum number of intervals so the remaining intervals do not overlap with each other.
Approach 1: Greedy by Earliest End Time (O(n log n) time, O(1) space)
The key observation: keeping the interval that finishes earliest leaves the most room for future intervals. Start by sorting intervals by their end time using sorting. Iterate through the intervals while tracking the end time of the last accepted interval. If the current interval starts before that end time, it overlaps and must be removed. Otherwise update the end pointer and keep it. This greedy decision works because choosing the earliest finishing interval always maximizes the number of non-overlapping intervals you can keep.
This approach relies on a classic interval scheduling strategy and only requires a single pass after sorting. The algorithm runs in O(n log n) time due to sorting and uses O(1) extra space (excluding input). Problems involving interval conflicts often combine array traversal with greedy decisions like this.
Approach 2: Dynamic Programming (O(n^2) time, O(n) space)
This method treats the problem similarly to finding the longest chain of compatible intervals. First sort intervals by start time. Define dp[i] as the maximum number of non-overlapping intervals that end with interval i. For each interval i, iterate over all previous intervals j. If intervals[j].end <= intervals[i].start, they do not overlap, so update dp[i] = max(dp[i], dp[j] + 1). After processing all intervals, the largest value in dp gives the maximum set of non-overlapping intervals.
The final answer equals total_intervals - max_non_overlapping. This solution is conceptually straightforward and highlights the relationship between interval scheduling and subsequence-style DP problems. However, the nested loop results in O(n^2) time and O(n) space.
Recommended for interviews: The greedy solution is the expected answer. Interviewers want to see if you recognize the interval scheduling pattern and apply sorting by end time. Mentioning the dynamic programming approach first can show deeper understanding, but implementing the O(n log n) greedy algorithm demonstrates strong algorithmic intuition.
Approach 1: Greedy Approach
The greedy approach involves sorting the intervals by their end times. Then, we iterate through the sorted list and count the number of overlapping intervals to remove. The idea is to always pick the interval with the earliest end time, which leaves more room for the remaining intervals.
Steps:
- Sort the intervals based on their end time.
- Initialize a variable to keep track of the end of the last added interval.
- Iterate through the sorted intervals and for each interval, check if it overlaps with the last added interval. If it does, increment the count of intervals to remove. If it doesn't, update the end time to the current interval's end time.
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[1])
end = float('-inf')
count = 0
for interval in intervals:
if interval[0] >= end:
end = interval[1]
else:
count += 1
return countimport java.util.Arrays;
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
count++;
} else {
end = intervals[i][1];
}
}
return count;
}
}#include <algorithm>
#include <vector>
using namespace std;
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] < end) {
++count;
} else {
end = intervals[i][1];
}
}
return count;
}function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[1] - b[1]);
let end = intervals[0][1];
let count = 0;
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < end) {
count++;
} else {
end = intervals[i][1];
}
}
return count;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *intervalA = *(int **)a;
int *intervalB = *(int **)b;
return intervalA[1] - intervalB[1];
}
int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
if (intervalsSize == 0) return 0;
qsort(intervals, intervalsSize, sizeof(int*), compare);
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervalsSize; i++) {
if (intervals[i][0] < end) {
count++;
} else {
end = intervals[i][1];
}
}
return count;
}using System;
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
if (intervals.Length == 0) return 0;
Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++) {
if (intervals[i][0] < end) {
count++;
} else {
end = intervals[i][1];
}
}
return count;
}
}The Python function first sorts intervals by their end values. It iterates over the intervals to update the 'end' and count overlapping ones. The key trick is maintaining the smallest 'end' to maximize selection of across iterations.
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(1), not considering input space.
Approach 2: Dynamic Programming Approach
This approach utilizes dynamic programming to solve the problem. It is typically less efficient than the greedy method but serves as an illustrative illustration of tackling overlap problems using dp.
- Sort intervals based on start time to ensure a consistent order for dp evaluation.
- Define a dp array where dp[i] stores the maximum count of non-overlapping intervals up to i-th interval.
- Initialize each dp[i] to 1 as each interval can at least be alone considered non-overlapping.
- For each interval, check whether it can be included in the non-overlapping list built so far without causing overlap.
- The answer will be determined by the maximum value in the dp array.
def eraseOverlapIntervals(intervals):
intervals.sort(key=lambda x: x[0])
n = len(intervals)
dp = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
max_non_overlapping = max(dp)
return n - max_non_overlappingimport java.util.Arrays;
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
int n = intervals.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxCount = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxCount = Math.max(maxCount, dp[i]);
}
return n - maxCount;
}
}#include <vector>
#include <algorithm>
using namespace std;
int maxNonOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end());
vector<int> dp(intervals.size(), 1);
int maxCount = 1;
for (size_t i = 1; i < intervals.size(); ++i) {
for (size_t j = 0; j < i; ++j) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxCount = max(maxCount, dp[i]);
}
return intervals.size() - maxCount;
}function eraseOverlapIntervals(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
let n = intervals.length;
let dp = Array(n).fill(1);
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
let maxNonOverlap = Math.max(...dp);
return n - maxNonOverlap;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *intervalA = *(int **)a;
int *intervalB = *(int **)b;
return intervalA[0] - intervalB[0];
}
int maxNonOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
if (intervalsSize == 0) return 0;
qsort(intervals, intervalsSize, sizeof(int*), compare);
int* dp = malloc(intervalsSize * sizeof(int));
int maxCount = 1;
for (int i = 0; i < intervalsSize; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = fmax(dp[i], dp[j] + 1);
}
}
maxCount = fmax(maxCount, dp[i]);
}
free(dp);
return intervalsSize - maxCount;
}using System;
public class Solution {
public int EraseOverlapIntervals(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
int n = intervals.Length;
int[] dp = new int[n];
Array.Fill(dp, 1);
int maxCount = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
maxCount = Math.Max(maxCount, dp[i]);
}
return n - maxCount;
}
}The Python calculation sorts intervals and applies nested loops to fill a dp array with the maximum number of non-overlapping subsequences possible within the designated comparisons among start and end times.
Time Complexity: O(n^2) due to the nested loop construction.
Space Complexity: O(n) for storing dp results.
Approach 3: Sorting + Greedy
We first sort the intervals in ascending order by their right boundary. We use a variable pre to record the right boundary of the previous interval and a variable ans to record the number of intervals that need to be removed. Initially, ans = intervals.length.
Then we iterate through the intervals. For each interval:
- If the left boundary of the current interval is greater than or equal to
pre, it means that this interval does not need to be removed. We directly updatepreto the right boundary of the current interval and decrementansby one; - Otherwise, it means that this interval needs to be removed, and we do not need to update
preandans.
Finally, we return ans.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the number of intervals.
function eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]);
let [ans, pre] = [intervals.length, -Infinity];
for (const [l, r] of intervals) {
if (pre <= l) {
--ans;
pre = r;
}
}
return ans;
}func eraseOverlapIntervals(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][1] < intervals[j][1]
})
ans := len(intervals)
pre := math.MinInt32
for _, e := range intervals {
l, r := e[0], e[1]
if pre <= l {
ans--
pre = r
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n log n) due to the sort operation. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to the nested loop construction. |
| Sorting + Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy (Sort by End Time) | O(n log n) | O(1) | Best general solution. Optimal for interview settings and large inputs. |
| Dynamic Programming | O(n^2) | O(n) | Useful for understanding interval compatibility or when exploring DP formulations. |
Frequently asked questions
Is Non-overlapping Intervals easy or hard?
Non-overlapping Intervals is rated Medium on LeetCode. The implementation is short, but the challenge is recognizing the greedy strategy of sorting by end time. Candidates who identify the interval scheduling pattern typically solve it quickly.
How to solve Non-overlapping Intervals in O(n)?
A strict O(n) solution is generally not possible because the intervals must be ordered first. The standard approach sorts intervals by end time, which costs O(n log n). If the intervals were already sorted by end time, the greedy scan itself would run in O(n).
What is the best approach for Non-overlapping Intervals?
The greedy approach that sorts intervals by end time is the optimal solution. After sorting, iterate through the intervals and keep track of the last selected end time. If an interval overlaps, remove it; otherwise keep it. This algorithm runs in O(n log n) time and O(1) extra space.
What data structure is used in Non-overlapping Intervals?
The solution mainly uses arrays to store intervals and sorting algorithms to order them by end time. The greedy approach only tracks the last chosen end value, while the dynamic programming approach uses an additional DP array to store optimal subproblem results.
What is the time complexity of Non-overlapping Intervals?
The optimal greedy solution runs in O(n log n) time due to sorting the intervals. After sorting, the algorithm scans the list once in O(n). The dynamic programming alternative takes O(n^2) time because it compares each interval with all previous ones.
Non-overlapping Intervals Python or Java solution approach?
In both Python and Java, the common solution sorts the interval list using a custom comparator based on the end value. Then iterate through the sorted intervals while tracking the last non-overlapping end. If the current start is smaller than the previous end, increment the removal count.
Is Non-overlapping Intervals asked at Google, Amazon, or Meta?
Interval scheduling and overlap removal problems appear frequently in interviews at companies like Google, Amazon, Meta, and Microsoft. The question tests understanding of greedy strategies, sorting, and recognizing optimal substructure in interval problems.