Remove the Fewest Overlapping Intervals

You are given an array of intervals intervals, where each interval is [start, end] with start < end. Return the minimum number of intervals that must be removed so that all remaining intervals are pairwise non-overlapping.

Intervals that only touch at an endpoint do not overlap. For example, [1, 2] and [2, 4] may both remain.

Implement minIntervalsToRemove(intervals).

Constraints

• 1 <= intervals.length <= 200,000
• -10^9 <= start < end <= 10^9
• Duplicate intervals are allowed and occupy separate positions.
• Return one integer.

Example 1

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

Removing [1, 3] leaves three intervals that touch only at endpoints.

Example 2

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

Only one of the three identical intervals can remain.

Remove the Fewest Overlapping Intervals

Hints

1. Minimizing removals is the same as maximizing how many intervals remain.
2. Among intervals available to keep next, consider which ending time leaves the most room.

Approach

Maximizing the number kept is equivalent to minimizing removals. Sort intervals by ascending end time and greedily retain an interval whenever its start is at least the end of the most recently retained interval. Choosing the available interval that ends first leaves at least as much room for every later choice as any alternative, so an exchange argument preserves an optimal solution after each selection. Subtract the maximum kept count from the original length.

• Time complexity: O(n log n) for sorting n intervals; the greedy scan is O(n).
• Space complexity: O(n) for a sorted copy of the intervals, excluding sort implementation overhead.