All problems

Non-overlapping Intervals

Medium · greedy

You are given a list intervals, where each item [start, end] covers the time from start up to, but not including, end. Two intervals overlap when they share some moment in time. Intervals that only touch, like [1, 2] and [2, 3], do not overlap.

Return the minimum number of intervals you must remove so that the intervals left over do not overlap each other.

The intervals come in no particular order. If nothing overlaps already, the answer is 0.

Examples

Example 1

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

Output: 1

Remove [1, 3]. What is left, [1, 2], [2, 3] and [3, 4], only touches end to start.

Example 2

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

Output: 2

All three are the same interval. Keep one and remove the other two.

Example 3

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

Output: 0

The intervals touch at 2 but do not overlap, so nothing has to go.

Constraints

• 1 <= len(intervals) <= 10^4
• intervals[i] has exactly two numbers, start and end
• -10^6 <= start < end <= 10^6