HARD Lab · Intervals · 50

435. Non-overlapping Intervals

Find the minimum number of intervals to remove so the rest are non-overlapping. The greedy trick is sorting by end time — not start — so you always keep the interval that finishes earliest and leaves the most room for future ones.

● MediumGreedyIntervalsTypeScript

PROBLEM What we're solving

Given an array of intervals [start, end], return the minimum number of intervals you must remove so that no two remaining intervals overlap. Example: [[1,2],[2,3],[3,4],[1,3]] → remove [1,3] (1 removal). Example: [[1,2],[1,2],[1,2]] → remove 2, keep one. Two intervals that only share an endpoint ([1,2] and [2,3]) do not overlap.

KEY IDEA Always keep the interval that ends soonest

Insight → sort by end time and greedily keep each interval whose start is ≥ the end of the last kept interval. The interval that ends earliest is always at least as good a choice as any other — it can only block fewer future intervals. This reduces the problem to counting how many you skip (remove), which equals n − (max non-overlapping kept).

RECIPE Sort by end, scan once, count removals

  • 0 · Edge case. Empty input → 0.
  • 1 · Sort by end. intervals.sort((a,b) => a[1]-b[1]). This ordering is the entire insight — the first interval in the sorted list is always safe to keep.
  • 2 · Initialise. lastEnd = intervals[0][1], removed = 0.
  • 3 · Scan i = 1 … n−1. If intervals[i][0] >= lastEnd: no overlap → keep, set lastEnd = intervals[i][1]. Otherwise: overlap → increment removed (the current interval ends later and is strictly worse to keep).
  • 4 · Return removed.
Classic confusion → many people sort by start time, which seems natural but is wrong. Consider [[1,10],[2,3],[3,5]]. Sorted by start: [1,10] comes first and you keep it, forcing removal of two more. Sorted by end: [2,3]comes first, you keep all three. Start-sorting maximises the "hole" in the future; end-sorting minimises it. Always sort by end.
Pattern transfer → the same end-sort greedy powers Minimum Number of Arrows to Burst Balloons (LC 452 — count groups of overlapping intervals), Meeting Rooms II (min rooms = max overlapping at one instant), and the classic Activity Selection problem from algorithm textbooks.

COST Complexity & alternatives

Brute force (try all subsets)
O(2ⁿ)
Exponential. Infeasible for large n.
Greedy (sort by end)
O(n log n)
Dominated by sorting; O(1) extra space.

After sorting the single scan is O(n). Total: O(n log n) time, O(1) space (or O(n) if the sort is not in-place, e.g. in JS environments). There is no sub-quadratic DP approach that beats the greedy here — the exchange-argument proof shows the greedy is optimal.

RUN IT Greedy: sort by END, keep if no overlap

step 0 / 5
STARTSort 4 intervals by end time. Sorting by end (not start) ensures we always commit to the interval that ends soonest — leaving maximum room for the future.
sorted by end →1-202-311-323-43
State
−∞
lastEnd
0
removed
currently evaluatingkept (no overlap)removed (overlaps)
slowfast

TYPESCRIPT The solution, annotated

eraseOverlapIntervals.ts
function eraseOverlapIntervals(intervals: number[][]): number {
  if (intervals.length === 0) return 0;

  // Sort by END time — greedy optimality: commit to the interval
  // that ends soonest, leaving the most room for future intervals.
  intervals.sort((a, b) => a[1] - b[1]);

  let removed = 0;
  let lastEnd = intervals[0][1]; // end of the last kept interval

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] >= lastEnd) {
      // No overlap: keep this interval, advance the boundary
      lastEnd = intervals[i][1];
    } else {
      // Overlap: remove this interval (it ends later — keeping it
      // would only block more future intervals)
      removed++;
    }
  }

  return removed;
}

Reading it block by block

Line 2 — quick exit. No intervals means nothing to remove; return 0 immediately.
Lines 6–7 — sort by end time. This is the entire algorithm in one line. The comparator a[1] - b[1] puts the earliest-ending interval first. Every correctness guarantee flows from this ordering.
Lines 9–10 — initialise state. The first interval (earliest end) is always safe to keep, so lastEnd starts at its end value. removed starts at 0.
Lines 12–20 — greedy scan. For each subsequent interval: if its start ≥ lastEnd there is no overlap — keep it and advance lastEnd. Otherwise it overlaps the last kept interval; because we sorted by end the current interval ends at least as late, so removing it (not the previous one) is always the correct greedy choice.
Line 22 — return. removed is the minimum number of intervals that must be deleted.
Complexity → O(n log n) time (one sort + one linear scan), O(1) extra space. The inner loop body is O(1) — no nested work.

INTERVIEWFollow-ups they'll ask

  • "Return the actual intervals to remove, not just the count." Track which indices were skipped during the scan and collect them into a result array.
  • "What if you must remove exactly k intervals?" Greedy still applies — keep the same sorted order and stop once you have removed k; the answer is whether the remaining set is overlap-free.
  • "Minimum number of arrows to burst balloons (LC 452)?"Same end-sort greedy: count how many non-overlapping "groups" exist — each group needs one arrow.
  • "Why does sorting by start fail?" A long interval starting early (e.g. [1,100]) would be kept first, blocking everything behind it. Sorting by end guarantees we always keep the interval with the smallest "footprint" on the future timeline.
  • "What if intervals can have equal endpoints?" The condition start >= lastEnd already handles touching endpoints correctly — they are not considered overlapping per the problem statement.

MNEMONIC The one-liner

"End-sort first — the interval that ends soonest is never a worse choice. Skip anything that bites into the last kept end."

TRIGGERS When you see ___ → reach for ___

"minimum removals" over intervalssort by end, greedy scan
maximize non-overlapping intervals keptend-sort + keep if start ≥ lastEnd
interval scheduling / activity selectiongreedy by earliest finish time
arrows to burst balloons (LC 452)same end-sort, count groups

SKELETON The reusable shape

skeleton.ts
// Sort by END (not start!)
intervals.sort((a, b) => a[1] - b[1]);

let removed = 0;
let lastEnd = intervals[0][1];

for (let i = 1; i < intervals.length; i++) {
  if (intervals[i][0] >= lastEnd) {
    lastEnd = intervals[i][1];  // keep, advance boundary
  } else {
    removed++;                   // overlap, remove
  }
}
return removed;

FLASHCARDS Tap to flip

Why sort by end, not start?
Sorting by end ensures the kept interval finishes as early as possible, leaving the most room for future intervals. Sorting by start can force keeping a long early interval that blocks many later ones.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
Why must you sort intervals by end time rather than start time?
QUESTION 02
Trace [[1,2],[2,3],[3,4],[1,3]]. How many intervals are removed?
QUESTION 03
What is the time complexity of the greedy solution?
QUESTION 04
Two intervals that only touch at one point, like [1,2] and [2,3], are considered:
QUESTION 05
After end-sorting, when the current interval overlaps the last kept interval, which interval do you remove?
QUESTION 06
[[1,100],[11,22],[1,11],[2,12]] — how many removals are needed?
QUESTION 07
LC 452 "Minimum Arrows to Burst Balloons" uses the same technique. What does each "non-overlapping group" correspond to?