Intervals Merging and scheduling
508. Non-overlapping Intervals
You are given an array intervals, where intervals[i] = [start, end] is a span of time that begins at
start and ends at end. Return the fewest intervals you must remove so that no two of the remaining
intervals overlap.
Two intervals overlap when one begins before the other ends. An interval may begin at the moment another one
ends, so [1,3] and [3,5] do not overlap. This is not the rule of Merge Intervals, where intervals that
touch are merged.
Example 1
Input: intervals = [[2, 7], [1, 3], [3, 5], [6, 9], [5, 6]]
1Explanation: Removing [2,7] is enough. The other four, [1,3], [3,5], [5,6] and [6,9], only touch one after
another.
Example 2
Input: intervals = [[3, 8], [3, 8], [3, 8]]
2Explanation: Equal intervals overlap each other, so only one of the three copies can stay.
Example 3
Input: intervals = [[-10, -5], [-5, 0], [0, 5]]
0Explanation: Each interval begins exactly when the one before it ends, so nothing overlaps. Times can be negative.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ intervals.length ≤ 105intervals[i].length = 2-109 ≤ start < end ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.