Non-overlapping Intervals
Part of Practice: Insert & Merge
You are given a list of intervals, each a pair [start, end]. Remove the minimum number of intervals so that the survivors do not overlap, and return that minimum count. Here, intervals that only touch at a boundary — like [1, 2] and [2, 3] — do NOT count as overlapping, which is the opposite convention from the merge-intervals problem.
Constraints that matter: up to 100,000 intervals, so the solution needs to be O(n log n). Removing the minimum number of intervals is the same as keeping the maximum number of pairwise non-overlapping ones.
Examples
- Input:
- intervals = [[1,2],[2,3],[3,4],[1,3]]
- Output:
- 1
Remove [1,3]; the remaining [1,2], [2,3], [3,4] only touch at endpoints, which is allowed.
- Input:
- intervals = [[1,2],[1,2],[1,2]]
- Output:
- 2
Only one copy of [1,2] can stay; the other two must go.
- Input:
- intervals = [[1,2],[2,3]]
- Output:
- 0
Touching at 2 is not an overlap, so nothing needs removing.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.