Non-overlapping Intervals
MediumKeep the most, so remove the fewest
Problem
Given intervals, return the minimum number to remove so the rest are non-overlapping.
Keep intervals that end earliest; count the ones that clash and must be dropped.
The idea
Minimising removals is the same as maximising how many intervals you keep, which is activity selection: sort by end time and keep every interval starting after the last kept one. The removals are whatever is left over.
The trick
- Sort by end time — sorting by start gives the wrong answer.
- Answer = total - kept.
- Touching endpoints do not count as overlapping.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [[1,2],[2,3],[3,4],[1,3]] Values: 1, 2.
1sort by end2lastEnd=-inf; remove=03for iv in intervals:4 if iv.start>=lastEnd: lastEnd=iv.end5 else: remove++6return removeInput
- array
- [1, 2]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- intervals = [[1,2],[2,3],[3,4],[1,3]]
- Output:
- 1
- Explanation:
- Remove [1,3] so the rest don't clash → 1.
Example 2
- Input:
- intervals = [[1,2],[1,2],[1,2]]
- Output:
- 2
- Explanation:
- Two of the three must go → 2.
Example 3
- Input:
- intervals = [[1,2],[2,3]]
- Output:
- 0
- Explanation:
- They only touch → remove 0.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.