Fewest intervals to remove

mediumSort by start and sweepGreedy choiceSorting target 25 min

Fewest intervals to remove

Not solved yetLeetCode 435. Non-overlapping Intervals

Each item of intervals is a pair [start, end] with start < end. Think of it as a booking of one room from start until end. Two bookings clash when each one starts before the other ends. A booking that ends at 4 and one that starts at 4 do not clash: the first is over when the second begins. The bookings come in any order.

Remove as few bookings as you can so that no two of the bookings left clash, and return how many you removed.

This endpoint rule is the opposite of merge intervals, where touching intervals merged. Check the rule in every interval problem.

Example 1

Inputintervals = [[1, 3], [2, 4], [3, 5]]Output1

Remove [2, 4]. Then [1, 3] and [3, 5] only touch at 3, which is allowed.

Example 2

Inputintervals = [[1, 10], [2, 3], [4, 5], [6, 7]]Output1

Remove the long [1, 10]. The three short bookings fit one after another.

Example 3

Inputintervals = [[3, 6], [3, 6], [3, 6]]Output2

Equal bookings all clash with each other, so only one can stay.

Constraints

0 ≤ len(intervals) ≤ 10⁵
-5 × 10⁴ ≤ start < end ≤ 5 × 10⁴

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern