Non-overlapping Intervals

Sort Colors

Insert Interval

Remove the fewest intervals so the remaining schedule has no overlaps.

Given an array of intervals `intervals`, remove the minimum number of intervals so that the remaining intervals do not overlap. By this problem's convention, intervals that only touch at an endpoint (like `[1,2]` and `[2,3]`) are considered non-overlapping and may both stay.

## Example
```
Input: {"intervals":[[1,2],[2,3],[3,4],[1,3]]}
Output: 1
```

**Constraints**
- 0 <= intervals.length <= 100000
- -50000 <= start < end <= 50000
- The input order is arbitrary

**Follow-up**
Why does sorting by interval end time lead to the optimal greedy choice?

- Find the minimum number of intervals to delete so that none of the survivors overlap — equivalently, find the MAXIMUM number of mutually non-overlapping intervals you can keep, then subtract that count from the total.
- Intervals that only touch at an endpoint (like `[1,2]` and `[2,3]`) count as non-overlapping and may both survive.

Understand the Goal

- This is "activity selection": sort by end time and greedily keep the interval that finishes earliest whenever a conflict is found.
- The exchange argument: among any set of intervals that overlap, whichever one ends earliest leaves the most room for everything after it — swapping any other choice for the earliest-ending one can never make the remaining selection worse, so the greedy choice is always at least as good as any alternative.

Choose the Core Pattern

- Sort all intervals by end time ascending.
- Track `lastEnd`, the end time of the most recently kept interval, starting at negative infinity (or the first interval's end after keeping it).
- Scan left to right: if the current interval's start is >= `lastEnd`, it doesn't overlap the last kept interval — keep it and update `lastEnd` to its end. Otherwise it overlaps, so it must be removed; do not update `lastEnd` (the interval already kept still ends earlier, so it stays the better anchor).
- The answer is `total intervals - kept count`.

Build the Algorithm

- 0 or 1 intervals: nothing can overlap, so 0 removals.
- All intervals identical or fully nested: only the true earliest-ending interval survives per overlapping cluster; every other overlapping one gets removed.
- Intervals that only touch at endpoints (`[1,2]`, `[2,3]`): the `>=` comparison (not `>`) on start vs. `lastEnd` must treat these as non-overlapping, or the count will be wrong.

Check Edge Cases

- Time complexity is O(n log n).
- Space complexity is O(1) beyond the sort output model.