Typorithm · medium

Non-Overlapping Intervals

non-overlapping-intervalsintervalssort-by-endgreedykeep-earliest-end

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Non-Overlapping Intervals

Intervals

Sort by end; greedily keep each interval that starts after the last kept end, counting the rest as removals.

To remove the fewest intervals, keep as many compatible ones as possible.

Sorting by end and always keeping the interval that finishes earliest leaves the most room for the rest.

Any interval starting before the last kept end conflicts and is counted as a removal.

Sort by END, not start.

Keep the earliest-ending compatible interval.

Count conflicts as removals.

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let prevEnd = -Infinity;
  let removed = 0;

  for (const [start, end] of intervals) {
    if (start >= prevEnd) {
      prevEnd = end;
    } else {
      removed += 1;
    }
  }

  return removed;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Sort by end

Sorting by end lets you greedily keep the interval that frees up soonest.

intervals.sort((a, b) => a[1] - b[1])

2. Compatible

If this interval starts after the last kept end, keep it.

if (start >= prevEnd) {

3. Advance boundary

Update the boundary to the kept interval's end.

prevEnd = end

4. Drop overlap

An overlapping interval is removed instead.

removed += 1

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.