DSA Tracker

Visualize

Non-overlapping Intervals

time O(n log n)space O(n)

The insight: to keep the most intervals — and therefore remove the fewest — always keep whichever conflicting interval ends soonest. An interval that ends earlier leaves more room for everything that comes after it, so it's never a worse choice than one that ends later. Sorting by end time and greedily accepting any interval that starts at or after the last kept interval's end applies that rule automatically, so whatever gets skipped along the way is exactly the minimum set that had to be discarded. Sorted order: [[1,2], [2,3], [1,3], [3,4]] with ends 2,3,3,4 (tie at end=3 keeps [2,3] before [1,3]); minimum removals = 1.

Details

Animated on: Given an array of intervals, find the minimum number of intervals to remove to make the rest non-overlapping.

Problem:Non-overlapping IntervalsMedium

Pattern:Intervals

Intervals

step 1 / 6

[1,2]
[0]
[2,3]
[1]
[1,3]
[2]
[3,4]
[3]

Sort intervals by end time. Sorted order: [[1,2], [2,3], [1,3], [3,4]] (ends: 2, 3, 3, 4). Tie at end=3 keeps original relative order [2,3] before [1,3].

  • i=0· arr[0] = [1,2]
Pseudocode
1FUNCTION minRemoveOverlapping(intervals):
2  (sort by end time)
3  sort intervals by their end value
4  kept = a list holding just the first interval
5  prevEnd = the end value of the first interval
6  FOR i from 1 up to the length of intervals:
7    start, end = the two values of intervals[i]
8    IF start >= prevEnd:  (no overlap with the last kept)
9      add intervals[i] to kept
10      prevEnd = end
11    END IF
12  END FOR
13  RETURN (length of intervals) minus (length of kept)
14END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 6 steps
  1. Sort intervals by end time. Sorted order: [[1,2], [2,3], [1,3], [3,4]] (ends: 2, 3, 3, 4). Tie at end=3 keeps original relative order [2,3] before [1,3].
  2. Initialize: keep the first interval [1,2] (end=2). prevEnd = 2. Start from the second interval (idx=1).
  3. Consider interval [2,3] (idx=1). Start=2 >= prevEnd=2? Yes — keep it! Update prevEnd = 3.
  4. Consider interval [1,3] (idx=2). Start=1 < prevEnd=3? Overlap! Discard this interval. Removals count = 1 so far.
  5. Consider interval [3,4] (idx=3). Start=3 >= prevEnd=3? Yes — keep it. All intervals processed.
  6. Kept [1,2], [2,3], [3,4]; discarded [1,3] (the only one that overlapped). Minimum removals = 1.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Non-overlapping Intervals in the editorAll Intervals problemsBack to roadmap