M.A.T.R.I.X

Appearance

Volume ITechnology

4.27.3 — Non-overlapping Intervals ​

LeetCode 435 · Medium

The problem ​

Return the minimum number of intervals to remove so that the rest do not overlap.

Restating the Problem: You are given a collection of intervals. Some of them overlap, creating conflicts. You want to find the absolute minimum number of intervals you need to throw away so that the remaining intervals have zero overlaps.

  • Constraints to note: The array length is up to 10^5, meaning an O(n^2) approach will time out. We need an O(n \log n) sorting-based solution.
  • Edge cases: No intervals might overlap (return 0). All intervals might overlap each other perfectly (keep exactly 1, remove the rest).
[[1,2],[2,3],[3,4],[1,3]]   →  1     (remove [1,3])
[[1,2],[1,2],[1,2]]         →  2
[[1,2],[2,3]]               →  0     (touching is not overlapping here)

Brute Force Approach ​

The naive approach is to consider every possible subset of the given intervals. For a set of n intervals, there are 2^n possible subsets. For each subset, you check if any intervals overlap. Among all valid non-overlapping subsets, you pick the one with the largest number of intervals. This O(n \cdot 2^n) approach is hopelessly slow for anything beyond very small inputs.

The pattern ​

Turn it round: removing the fewest is the same as keeping the most. So the question becomes what is the largest set of non-overlapping intervals I can keep? — and the answer is n minus that.

That is the activity selection problem, and it has a famous greedy:

Sort by end time, and always keep the interval that finishes earliest among those that still fit.

Why sort by end, not by start ​

This is the question, so here is the proof.

Finishing earliest leaves the most room for everything after it.

Formally, an exchange argument. Suppose some optimal solution does not include the interval that finishes earliest, call it x. Take the first interval in that solution, call it y. Since x finishes no later than y, swapping y for x cannot create a conflict with anything later — everything that fitted after y also fits after x. So there is an optimal solution containing x, and greedy is safe.

Sorting by start fails, and it is worth seeing why: a very long interval starting first would be taken and would block everything else. [[1,100],[2,3],[4,5]] — sorting by start keeps only [1,100]; sorting by end keeps two.

Sorting by length also fails. [[1,10],[9,12],[11,20]] — the shortest is [9,12], and taking it blocks both others, whereas keeping [1,10] and [11,20] gives two.

Having both counterexamples ready is a strong way to answer "why end time".

The solution ​

python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])           # sort by END

        kept = 0
        last_end = float('-inf')

        for start, end in intervals:
            if start >= last_end:                     # no overlap with what we kept
                kept += 1
                last_end = end

        return len(intervals) - kept
ts
function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);

  let kept = 0, lastEnd = -Infinity;

  for (const [start, end] of intervals) {
    if (start >= lastEnd) {
      kept++;
      lastEnd = end;
    }
  }

  return intervals.length - kept;
}

start >= last_end uses >=, because touching intervals do not overlap in this problem — [1,2] and [2,3] can both be kept. Compare 4.27.2 Merge Intervals, where touching intervals do merge and the comparison is <=. Two adjacent problems, opposite conventions — this is exactly why you ask.

last_end starts at negative infinity, so the first interval is always kept.

Code Walkthrough:

  • Sorting: We sort the intervals by their end times. This is the greedy choice that guarantees we leave the maximum possible room for subsequent intervals.
  • Initialization: We keep a counter kept = 0 and track the last_end of the interval we decided to keep (initialized to negative infinity).
  • Iteration: We loop through each start and end in the sorted intervals.
  • Overlap Check (start >= last_end): If the current interval's start is greater than or equal to our last_end, it means it doesn't conflict with the last interval we kept. We keep this new interval, increment kept, and update last_end to its end.
  • Return: The number of intervals we must remove is the total number of intervals minus the number we kept.

Counting kept intervals and subtracting is cleaner than counting removals, because the greedy naturally decides what to keep.

Trace ​

[[1,2],[2,3],[3,4],[1,3]] sorted by end: [[1,2],[1,3],[2,3],[3,4]].

intervallast_endkeep?kept
[1,2]−∞yes1, end 2
[1,3]21 < 2 → no1
[2,3]22 ≥ 2 → yes2, end 3
[3,4]33 ≥ 3 → yes3, end 4

Kept 3, removed 4 − 3 = 1 ✓.

Complexity ​

O(n \log n) time from the sort, O(1) extra space.

  • Time Complexity: O(n \log n). The time is completely dominated by the sorting step. The greedy linear scan takes O(n) time.
  • Space Complexity: O(1) extra space (excluding the space required by the sorting algorithm itself), because we only use a few integer variables (kept, last_end).

The other interval greedy ​

The mirror problem — Minimum Number of Arrows to Burst Balloons (LeetCode 452) — is the same algorithm with the answer read differently.

You want the fewest points that touch every interval. Sort by end, shoot an arrow at the end of the first interval, skip everything it hits, and repeat. The number of arrows equals the number of intervals you would have "kept" here.

They are the same computation: the count of intervals kept is both the largest non-overlapping set and the fewest points needed to stab all of them. That duality is a nice thing to notice, and it is why the two problems have identical code.

Watch one detail there: touching balloons are burst by the same arrow, so the comparison flips to >.

Where this goes next ​

  • Merge Intervals — sort by start instead. 4.27.2.
  • Maximum Length of Pair Chain — identical to this problem, counting kept pairs directly.
  • Minimum Arrows to Burst Balloons — above.
  • Job Scheduling with profits — when intervals have values, greedy fails and it becomes DP with binary search, O(n \log n). That is the boundary: unweighted activity selection is greedy; weighted is DP. Naming it shows you know where the greedy stops working.

What the interviewer will push on ​

"Why sort by end?" The exchange argument, plus the [[1,100],[2,3],[4,5]] counterexample against sorting by start.

"Why not sort by length?" [[1,10],[9,12],[11,20]].

"Does touching count as overlapping?" Not here — hence >=. And it is the opposite convention to Merge Intervals, so ask on every interval problem.

"Why count kept rather than removed?" The greedy decides what to keep; removals are the leftover.

"What if intervals had weights?" Greedy breaks; it becomes DP with binary search.

One thing to volunteer: give the exchange argument before the code. This is the chapter where greedy proofs are short and expected, and one sentence of justification separates a correct solution from a lucky one.

Next: 4.27.4 Meeting Rooms — the simplest interval question there is, and the warm-up for the one after it.