Non-overlapping Intervals

This problem looks like Merge Intervals and is solved very differently. It is a greedy problem in disguise — the classic interval-scheduling problem — and the whole difficulty is choosing the right sort key.

The problem

Given a list of intervals, return the smallest number of intervals you must remove so that the rest do not overlap. Intervals that only touch, like [1, 2] and [2, 3], do not overlap.

• [[1, 4], [2, 3], [3, 6], [5, 7], [6, 8]] → 2. Keep [2, 3], [3, 6] and [6, 8]; remove [1, 4] and [5, 7].
• [[1, 2], [1, 2], [1, 2]] → 2. Only one copy can stay.

Constraints: 1 ≤ n ≤ 10⁵, start < end.

Clarifying questions

• Do touching intervals overlap? No, [1, 2] and [2, 3] can both stay.
• Do I return the count or the intervals removed? The count.
• Are the intervals sorted? No.

Approach 1: try every group to keep

Removing the fewest is the same as keeping the most. The simple way is to try groups from the largest size down and return as soon as one group has no overlaps.

1from itertools import combinations23def erase_overlap_brute(intervals: list[list[int]]) -> int:4    """Try keeping as many as possible, largest group first."""5    n = len(intervals)6    for keep in range(n, 0, -1):7        for group in combinations(intervals, keep):8            ordered = sorted(group)9            if all(b[0] >= a[1] for a, b in zip(ordered, ordered[1:])):10                return n - keep11    return 0

There are 2ⁿ groups, and each check sorts and scans the group, so this is O(2ⁿ × n log n). At n = 30 it is already a billion groups; at n = 10⁵ it would never finish. A smarter exact method is dynamic programming over intervals sorted by start, O(n²) — still too slow at 10⁵.

The key insight

Build the kept set from left to right. At each step, ask: which interval should I keep next? Three rules come to mind, and only one works.

• Keep the shortest first. Wrong. On [[1, 5], [4, 7], [6, 10]], the shortest is [4, 7], and it clashes with both others: 2 removals. Keeping [1, 5] and [6, 10] needs only 1.
• Keep the one that starts first. Wrong. On [[1, 10], [2, 3], [4, 5]], [1, 10] starts first and blocks both others: 2 removals. Keeping [2, 3] and [4, 5] needs only 1.
• Keep the one that ends first. Right. The interval that finishes earliest leaves the most room for everything after it.

Why "ends first" is always safe — the exchange argument. Take any best solution. Look at its first kept interval, o. The interval g that ends earliest of all ends no later than o does. Swap o for g. Nothing breaks: g ends no later, so it clashes with nothing that o didn't clash with. The solution is just as large and now starts with g. So some best solution always starts with the greedy choice, and the same argument repeats for the rest. The Greedy section develops this proof style in full.

See it on the example. The set [1, 4], [6, 8] has no overlaps. Swap [1, 4] for [2, 3], which ends earlier: [2, 3], [6, 8] is still fine — and now [3, 6] fits between them, which it could not before. Ending earlier never hurts, and sometimes it opens room for one more.

Approach 2: sort by end, keep what fits

1def erase_overlap(intervals: list[list[int]]) -> int:2    """Greedy: sort by end, keep every interval that starts after the last kept end."""3    kept = 04    last_end = float("-inf")5    for start, end in sorted(intervals, key=lambda i: i[1]):6        if start >= last_end:                    # touching is allowed7            kept += 18            last_end = end9    return len(intervals) - kept

1. Sort by end.
2. Keep an interval if it starts at or after the end of the last one kept. Starting last_end at minus infinity means the first interval is always kept, with no special case.
3. Otherwise it is removed, and last_end stays where it is.
4. Return the number removed.

Dry run on [[1, 4], [2, 3], [3, 6], [5, 7], [6, 8]]. Sorted by end: [2, 3], [1, 4], [3, 6], [5, 7], [6, 8].

Removed: 5 - 3 = 2. Correct.

Complexity. O(n log n) for the sort, O(n) for the scan. Extra space O(1) beyond the sorted copy.

Approach 3: sort by start, drop the one that ends later

You can also sort by start. When the next interval clashes with the last kept one, remove whichever of the two ends later, and keep the one that ends sooner.

1def erase_overlap_by_start(intervals: list[list[int]]) -> int:2    """Sort by start; on a clash, remove the one that ends later."""3    removed = 04    last_end = float("-inf")5    for start, end in sorted(intervals, key=lambda i: i[0]):6        if start >= last_end:7            last_end = end8        else:9            removed += 110            last_end = min(last_end, end)        # keep the one that ends sooner11    return removed

This is the same greedy idea — prefer the earlier finish — applied at each clash. Same O(n log n). It is useful when the input is already sorted by start for another reason.

Edge cases

• One interval: kept; 0 removed.
• All identical, [[1, 2], [1, 2], [1, 2]]: the first is kept, the next two fail 1 >= 2; 2 removed.
• All touching in a chain, [[1, 2], [2, 3], [3, 4]]: >= keeps all three; 0 removed.
• One long interval over many short ones, [[1, 10], [2, 3], [4, 5]]: sorted by end, [1, 10] comes last and is removed.

Follow-ups

• "Minimum Number of Arrows to Burst Balloons." Same greedy by end, but touching balloons do overlap (one arrow at the shared point bursts both). Use start > last_end and return the number of kept groups, not the removals.
• "Each interval has a value; keep the set with the largest total value" (Weighted Interval Scheduling). Greedy no longer works. Sort by end and use dynamic programming, with binary search for the last compatible interval: O(n log n).
• "Return the intervals to remove." Collect the intervals that fail the test instead of counting them.