Non Overlapping Intervals

Medium · Intervals

You are given a list of intervals, each written as [start, end]. Find the smallest number of intervals you must remove so that none of the remaining intervals overlap each other. Two intervals only count as overlapping if their ranges share more than just a single touching endpoint.

Examples

Input:  intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Why:    Removing [1,3] leaves [1,2],[2,3],[3,4] which touch only at endpoints and do not overlap.

Input:  intervals = [[1,2],[1,2],[1,2]]
Output: 2
Why:    Two of the three identical intervals must be removed so only one remains.

Input:  intervals = [[1,2],[2,3]]
Output: 0
Why:    The intervals only touch at the boundary point 2, so nothing needs to be removed.

Constraints

1 <= intervals.length <= 10^5, intervals[i].length == 2, -5*10^4 <= start < end <= 5*10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Non Overlapping Intervals

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Non Overlapping Intervals. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.