Watch 10 video solutions for Non-overlapping Intervals, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by NeetCode has 168,282 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |