Non-overlapping IntervalsMedium

Non-overlapping Intervals

Medium 9.4k51% acceptance

ArrayIntervalsGreedySortingDynamic Programming

Given an array of intervals where intervals[i] = [startᵢ, endᵢ], return the minimum number of intervals you must remove so that the remaining intervals do not overlap.

Intervals that only touch at an endpoint — like [1,2] and [2,3] — are not considered overlapping.

Example 1

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

Output: 1

Remove [1,3] and the rest are non-overlapping.

Example 2

Input: intervals = [[1,2],[1,2],[1,2]]

Output: 2

Two of the three identical intervals must go.

Example 3

Input: intervals = [[1,2],[2,3]]

Output: 0

Touching at 2 is allowed.

Constraints

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
-5·10⁴ ≤ startᵢ < endᵢ ≤ 5·10⁴

Asked atGoogleAmazonMicrosoftBloomberg

JavaScript

⌘↵ to run

Loading editor…

Case 1

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

expected: 1

Case 2

[[1,2],[1,2],[1,2]]

expected: 2

Case 3

[[1,2],[2,3]]

expected: 0

Case 4

[[1,100],[11,22],[1,11],[2,12]]

expected: 2

Case 5

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

expected: 2

Case 6

[[1,2]]

expected: 0

Case 7

[[-100,-50],[-40,-20],[-30,10]]

expected: 1