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 * 104Problem 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.
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:
This C implementation sorts the intervals based on their end times using qsort. It then iterates through the sorted intervals, maintaining a count of the overlapping intervals to be removed and updating the end of the last included interval.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.
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.
This C solution sorts the intervals by start time and uses a dp array to store the longest non-overlapping subsequence up to each interval. It checks each interval against those before it to see if it can be appended without leading to overlap.
Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.
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:
pre, it means that this interval does not need to be removed. We directly update pre to the right boundary of the current interval and decrement ans by one;pre and ans.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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n log n) due to sorting. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to nested loops for dp updates. |
| Sorting + Greedy | — |
| 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. |
Non-Overlapping Intervals - Leetcode 435 - Python • NeetCode • 168,282 views views
Watch 9 more video solutions →Practice Non-overlapping Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor