Asked at

Non-Overlapping Intervals

Hard
VerifiedArrayIntervalsGreedySorting~30 min

Given an array of intervals, return the minimum number of intervals to remove so that the rest are pairwise non-overlapping. Intervals that only touch at an endpoint (one’s end equals the next’s start) do not count as overlapping.

Sort by end and greedily keep the interval that finishes earliest. The input arrives as a single array number[][].

Examples

in[[1, 2], [2, 3], [3, 4], [1, 3]]
out1

Remove [1,3] and the remaining three are disjoint.

in[[1, 2], [1, 2], [1, 2]]
out2

Keep one copy of [1,2]; remove the other two.

Constraints

  • 0 ≤ intervals.length ≤ 10⁵
  • intervals[i] == [start, end] with start < end
  • -5 × 10⁴ ≤ start < end ≤ 5 × 10⁴

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.