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 * 104In #435 Non-overlapping Intervals, the goal is to remove the minimum number of intervals so that the remaining intervals do not overlap. A key observation is that choosing intervals with the earliest finishing time leaves more room for future intervals, making this a classic greedy + sorting problem.
A common strategy is to first sort the intervals based on their end times. Then iterate through them while tracking the end of the last accepted interval. If the current interval overlaps with the previous one, you count it as a removal; otherwise, you update the tracking end time. This greedy choice ensures you keep as many compatible intervals as possible.
An alternative way to think about the problem is through Dynamic Programming, similar to interval scheduling or longest chain problems. However, this approach is usually less efficient than the greedy method. The greedy solution achieves optimal results with O(n log n) time due to sorting and O(1) extra space (excluding sorting overhead).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy (Sort by End Time) | O(n log n) | O(1) |
| Dynamic Programming | O(n^2) | O(n) |
NeetCode
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:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.
1#include <algorithm>
2#include <vector>
3
4using namespace std;
5
6int eraseOverlapIntervals(vector<vector<int>>& intervals) {
7 if (intervals.empty()) return 0;
8 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
9 return a[1] < b[1];
10 });
11 int count = 0;
12 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;
}This C++ implementation uses the sort function with a custom comparator to sort the intervals by their end times. It tracks the end of the last non-overlapping interval and increments the overlap count if a new interval overlaps.
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.
Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval scheduling problems like Non-overlapping Intervals are commonly asked in FAANG and other top tech interviews. They test understanding of greedy algorithms, sorting, and reasoning about optimal substructure.
The optimal approach uses a greedy strategy by sorting intervals based on their end times. By always selecting the interval that finishes earliest, you maximize the number of non-overlapping intervals and minimize removals.
Sorting by end time ensures that the interval that frees up the timeline the earliest is chosen first. This greedy choice leaves maximum space for subsequent intervals and leads to the optimal solution.
Arrays or lists are typically used to store the intervals, and sorting utilities help order them by end time. Only simple variables are needed to track the previous interval’s end during iteration.
1def eraseOverlapIntervals(intervals):
2 intervals.sort(key=lambda x: x[0])
3 n = len(intervals)
4 dp = [1] * n
5 for i in range(n):
6 for j in range(i):
7 if intervals[j][1] <= intervals[i][0]:
8 dp[i] = max(dp[i], dp[j] + 1)
9 max_non_overlapping = max(dp)
10 return n - max_non_overlappingThe 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.