435. Non-overlapping Intervals

The phrase “minimum number to remove” is a trap — it makes you want to hunt for the intervals to delete. Flip it: the fewest you remove is whatever’s left over after you keep the most you can. That flip is the whole interval pattern, and it turns a fuzzy optimization into a two-line greedy scan.

The problem

You’re given a list of intervals, each a [start, end] pair. Some of them overlap. Return the minimum number you’d have to delete so that none of the survivors overlap. (Full statement on LeetCode.)

Take [[1,2], [2,4], [1,4]]. The [1,4] interval collides with both of the others, but [1,2] and [2,4] sit side by side and share only an endpoint. Drop [1,4] and you’re done — the answer is 1.

Intuition: keep the interval that frees you soonest

This is the classic activity-selection problem wearing a different hat. Instead of asking “which do I remove,” ask “how many can I keep without any overlap,” then subtract from the total. Same number, but the keep version has a clean greedy answer.

Here’s the greedy choice. Sort the intervals by their end value. Walk left to right and hold on to a end marker for the last interval you decided to keep. When the next interval starts before that marker, it overlaps — so it has to go, and you bump the removal count. When it starts at or after the marker, there’s no clash, so keep it and advance the marker to its end.

Why sort by end and not start? Because the interval that finishes earliest leaves the most room for everything after it. Every time you keep a small, early-ending interval, you maximize the space left on the number line for future picks. Greedily grabbing the earliest finish is provably optimal here — swap in any other choice and you can only do the same or worse.

One boundary decision matters: intervals that merely touch, like [1,2] and [2,3], do not count as overlapping. So the overlap test is a strict start < end, not <=.

Solution

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // Sort by end time. Integer.compare is a defensive habit over a[1] - b[1];
        // it doesn't overflow here (values fit well within int) but the habit travels.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int removed = 0;
        int end = intervals[0][1];   // end of the last interval we kept

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) {
                // Starts before the kept interval ends -> overlap, drop it.
                removed++;
            } else {
                // No clash; keep it and move the marker forward.
                end = intervals[i][1];
            }
        }

        return removed;
    }
}

The dropped interval never becomes the new marker — that’s the subtle part. When two intervals overlap, you always discard the one that ends later (it’s the current candidate, since we sorted by end, so the survivor is already the earlier-ending one you’re keeping). Leaving end untouched on a removal encodes exactly that.

Complexity

	Time	Space
Greedy after sort	$O(n \log n)$	$O(n)$

The sort dominates at $O(n \log n)$; the scan is a single $O(n)$ pass that tracks just one int. Space is $O(n)$, not $O(1)$: intervals is an int[][] (an object array), so Arrays.sort with a comparator runs TimSort, which allocates $O(n)$ temporary references.

In an interview

Say the reframing out loud first: “minimizing removals is the same as maximizing the non-overlapping set, which is activity selection.” That one line tells the interviewer you recognized the pattern instead of reaching for brute force. Then justify sorting by end time — earliest finish leaves the most room — before you write a single line.

The trap they’ll probe is the touching-endpoints case. Have an answer ready for whether [1,2] and [2,3] overlap, and let it drive your < versus <=; getting that backward silently over-counts removals. A second thing worth mentioning: prefer Integer.compare over a[1] - b[1] as a defensive habit — the subtraction is safe within this problem’s bounds, but it silently overflows once endpoints span the full int range, so it’s a good reflex to carry into real code.

Sorting-by-end is the same move behind Meeting Rooms, where you’re checking whether any removals are needed at all. If you sort by start instead, you’re set up for Merge Intervals — the sibling that stitches overlaps together rather than deleting them. The interval pattern hub lays out when each sort key wins.

References

• LeetCode 435 — Non-overlapping Intervals