Given an array of intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Examples
Input:intervals = [[1,2],[2,3],[3,4],[1,3]]
Output:1
Remove [1,3] to make the rest non-overlapping.
Input:intervals = [[1,2],[1,2],[1,2]]
Output:2
Remove two [1,2]s to leave one valid interval.
Constraints
• 1 <= intervals.length <= 10^5
• intervals[i].length == 2
• -5 * 10^4 <= start_i < end_i <= 5 * 10^4
Complexity Analysis
Time
O(N log N)
sorting the intervals.
Space
O(1) auxiliary space (ignoring sort implementation details).