MediumIntervals · Greedy · DP

Non-overlapping Intervals

Given intervals, return the minimum number of intervals to remove so the rest don't overlap. Here intervals that only share an endpoint, like [1,2] and [2,3], do not overlap.

[[1,2],[2,4],[1,4]] → 1[[1,2],[2,4]] → 0

Try:
CALL
1 / 1

Code

The highlighted line runs next. The pill shows the live values in the running call.

Variables

The data structures the code is building

Number line

One row per interval; the intervals kept are collected below

Time and space complexity

n = len(intervals). The highlighted row is the solution being traced.

Keyboard: ← → step, Space play or pause. 1 to 8 intervals with start < end, values from −20 to 40, written as JSON.