# LeetCode 435: Non-overlapping Intervals

## Problem Restatement

We are given an array of intervals.

Each interval has a start and an end:

```python
[start, end]
```

We need to remove the minimum number of intervals so that the remaining intervals do not overlap.

Two intervals that only touch at an endpoint do not overlap.

For example:

```python
[1, 2]
[2, 3]
```

These can both remain, because the first interval ends exactly when the second interval starts.

The official problem asks us to return the minimum number of intervals that must be removed so the rest are non-overlapping.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `intervals`, a list of `[start, end]` pairs |
| Output | Minimum number of intervals to remove |
| Non-overlap rule | `[1, 2]` and `[2, 3]` do not overlap |
| Goal | Keep as many non-overlapping intervals as possible |

Example function shape:

```python
def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

```python
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
```

We can remove:

```python
[1, 3]
```

The remaining intervals are:

```python
[[1, 2], [2, 3], [3, 4]]
```

They do not overlap.

Answer:

```python
1
```

Example 2:

```python
intervals = [[1, 2], [1, 2], [1, 2]]
```

All intervals are identical. We can keep only one.

Answer:

```python
2
```

Example 3:

```python
intervals = [[1, 2], [2, 3]]
```

They only touch at endpoint `2`, so they do not overlap.

Answer:

```python
0
```

## First Thought: Try Every Subset

One way to think about the problem is:

Find the largest subset of intervals that do not overlap.

Then:

```python
answer = total_intervals - largest_non_overlapping_subset_size
```

But trying every subset is too slow.

For `n` intervals, there are:

```python
2 ** n
```

possible subsets.

We need a greedy method.

## Key Insight

To remove the fewest intervals, we should keep as many intervals as possible.

This is the classic interval scheduling problem.

The best greedy rule is:

Sort intervals by their end time, then keep every interval that starts after or at the end of the last kept interval.

Why sort by end time?

Because an interval that ends earlier leaves more room for future intervals.

For example:

```python
[1, 10]
[2, 3]
[3, 4]
[4, 5]
```

If we keep `[1, 10]`, we block many smaller intervals.

If we keep `[2, 3]`, we still have room for `[3, 4]` and `[4, 5]`.

So the greedy choice is to keep the interval with the earliest end.

## Algorithm

Sort intervals by end time:

```python
intervals.sort(key=lambda x: x[1])
```

Initialize:

```python
removed = 0
prev_end = intervals[0][1]
```

Then scan from the second interval.

For each interval `[start, end]`:

If:

```python
start < prev_end
```

then this interval overlaps with the last kept interval, so we remove it:

```python
removed += 1
```

Otherwise, we keep it and update:

```python
prev_end = end
```

Return:

```python
removed
```

Because the intervals are sorted by end time, when an overlap occurs, removing the current interval is safe. The previously kept interval ends no later than the current interval, so keeping the previous interval leaves at least as much room for future intervals.

## Correctness

After sorting by end time, the algorithm considers intervals from earliest finishing to latest finishing.

Whenever the current interval starts at or after `prev_end`, it does not overlap with the last kept interval. The algorithm keeps it, and this increases the number of kept intervals by one.

Whenever the current interval starts before `prev_end`, it overlaps with the last kept interval. Since the last kept interval has an end time less than or equal to the current interval’s end time, keeping the last kept interval is at least as good for all future intervals. It leaves the same or more remaining timeline available.

Therefore, in every overlap case, removing the current interval does not reduce the maximum possible number of intervals we can keep.

The algorithm greedily constructs a maximum-size set of non-overlapping intervals. Since the minimum number removed equals:

```python
len(intervals) - maximum_number_kept
```

the returned removal count is minimal.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` or `O(n)` | Depends on sorting implementation |

The scan after sorting is `O(n)`.

## Implementation

```python
class Solution:
    def eraseOverlapIntervals(self, intervals: list[list[int]]) -> int:
        intervals.sort(key=lambda x: x[1])

        removed = 0
        prev_end = intervals[0][1]

        for start, end in intervals[1:]:
            if start < prev_end:
                removed += 1
            else:
                prev_end = end

        return removed
```

## Code Explanation

We sort by interval end:

```python
intervals.sort(key=lambda x: x[1])
```

This lets us prefer intervals that finish earliest.

We keep the first interval after sorting:

```python
prev_end = intervals[0][1]
```

Then we scan the rest.

If the current interval starts before the previous kept interval ends:

```python
if start < prev_end:
```

the two intervals overlap, so we remove the current interval:

```python
removed += 1
```

Notice that we do not update `prev_end` in this case. The previous kept interval ends earlier or at the same time because of the sorting order.

If there is no overlap:

```python
else:
    prev_end = end
```

we keep the current interval and update the end boundary.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.eraseOverlapIntervals(
        [[1, 2], [2, 3], [3, 4], [1, 3]]
    ) == 1

    assert s.eraseOverlapIntervals(
        [[1, 2], [1, 2], [1, 2]]
    ) == 2

    assert s.eraseOverlapIntervals(
        [[1, 2], [2, 3]]
    ) == 0

    assert s.eraseOverlapIntervals(
        [[1, 100], [11, 22], [1, 11], [2, 12]]
    ) == 2

    assert s.eraseOverlapIntervals(
        [[-52, 31], [-73, -26], [82, 97], [-65, -11], [-62, -49], [95, 99], [58, 95], [-31, 49], [66, 98], [-63, 2], [30, 47], [-40, -26]]
    ) == 7

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Mixed overlap | Checks the standard case |
| Identical intervals | Keeps only one duplicate |
| Touching intervals | Confirms endpoint touching is allowed |
| Long interval blocking small intervals | Checks greedy end-time choice |
| Negative intervals | Checks ordering with negative values |