This problem focuses on finding the minimum removals required to make intervals non-overlapping. A state transition dynamic programming approach tracks the maximum number of intervals that can be kept, while a greedy strategy sorts intervals by end times for efficient removal decisions. Carefully managing overlaps ensures optimal removals while avoiding unnecessary deletions.
Problem Statement
Given an array of intervals where each interval is represented as [start, end], compute the minimum number of intervals to remove so that no two remaining intervals overlap. Intervals that only touch at their boundaries are considered non-overlapping.
For example, given intervals = [[1,2],[2,3],[3,4],[1,3]], removing [1,3] ensures the rest are non-overlapping. Your task is to implement a function that returns this minimum removal count efficiently, considering large input constraints.
Examples
Example 1
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
[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
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
You don't need to remove any of the intervals since they're already non-overlapping.
Constraints
- 1 <= intervals.length <= 105
- intervals[i].length == 2
- -5 * 104 <= starti < endi <= 5 * 104
Solution Approach
Sort Intervals by End Time
Begin by sorting intervals based on their end times. This ordering allows a greedy approach to pick the maximum number of non-overlapping intervals, which simplifies the calculation of how many intervals must be removed.
Dynamic Programming State Transition
Define dp[i] as the maximum number of non-overlapping intervals ending at the i-th interval. For each interval, check all previous intervals that end before its start and update dp[i] as dp[i] = max(dp[j] + 1) to maintain the optimal state transition.
Calculate Minimum Removals
Once the maximum count of non-overlapping intervals is known from the DP array or greedy selection, subtract this count from the total number of intervals. This difference is the minimum number of intervals to remove.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Sorting takes O(n log n) time, the DP approach can take O(n^2) in the worst case, but a greedy approach reduces it to O(n log n). Space complexity is O(n) for the DP array, and O(1) extra for the greedy method.
What Interviewers Usually Probe
- Do you consider intervals that only touch at endpoints as overlapping?
- Can you optimize the DP solution using a greedy approach for larger inputs?
- What is the trade-off between tracking maximum intervals kept vs. counting removals directly?
Common Pitfalls or Variants
Common pitfalls
- Assuming intervals touching at endpoints overlap, which leads to extra removals.
- Not sorting intervals properly before applying DP or greedy approach, causing incorrect state updates.
- Attempting a brute-force check of all subsets, which exceeds time limits for large inputs.
Follow-up variants
- Find the maximum number of non-overlapping intervals instead of minimum removals.
- Allow intervals with equal start and end times and count how many need removal.
- Apply the same logic to weighted intervals where each interval has a value and the goal is maximum total value non-overlapping.
How GhostInterview Helps
- Provides step-by-step DP and greedy strategies directly tied to the Non-overlapping Intervals pattern.
- Highlights common failure modes like endpoint overlaps and sorting issues for accurate solution refinement.
- Offers visual walkthroughs and interval examples to verify correctness without manual debugging.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
Do intervals that only touch count as overlapping in Non-overlapping Intervals?
No, intervals touching only at endpoints are considered non-overlapping and should not be removed.
Is sorting intervals necessary for the optimal solution?
Yes, sorting by end times enables the greedy approach and simplifies DP state transitions for efficiency.
What is the difference between DP and greedy approaches for this problem?
DP tracks the maximum intervals that can be kept considering all prior compatible intervals, while greedy chooses the earliest ending interval to minimize removals efficiently.
How do I handle very large input sizes up to 10^5?
Use the greedy end-time approach to achieve O(n log n) time, avoiding the O(n^2) DP computation for large arrays.
Can this problem pattern be applied to other interval scheduling problems?
Yes, the state transition dynamic programming pattern and greedy end-time strategy generalize to various interval selection and removal problems.
Need direct help with Non-overlapping Intervals instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Non-overlapping Intervals from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Determine the maximum length of a chain formed by pairs using dynamic programming and greedy sorting techniques efficiently.
Open problem page#1262 Greatest Sum Divisible by ThreeFind the maximum sum divisible by three from a given array using dynamic programming and state transition.
Open problem page#1363 Largest Multiple of ThreeFind the largest number divisible by three by selecting and ordering digits optimally using state transition dynamic programming techniques.
Open problem page