> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/non-overlapping-intervals.md).

# Non-overlapping Intervals

## Question ([LC.435](https://leetcode.com/problems/non-overlapping-intervals/)) 

> Given a list of intervals, find the minimum number of intervals that you need to removed to make the rest of the intervals non-overlapping. 

## Example 

```
I: intervals = [[1,2],[2,3],[3,4],[1,3]]
O: 1

I: intervals = [[1,2],[1,2],[1,2]]
O: 2

I: intervals = [[1,2],[2,3]]
O: 0 
```

## Approach 

Finding minimum is an optimization question so likely to be DP or greedy. 

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LtpqP4Bii7DT_BTd4fN%2Fuploads%2FaBfCBIlZhSQ9W3MFOssA%2Fnon-overlapping%20intervals.jpg?alt=media\&token=f3bf7d58-cfdd-4810-9662-aa0c870d9389)

We can assume there is an optimal solution such as by removing a set of intervals $$S$$. 

By exchange argument, we can swap out an interval $$R\_i$$ from the removing set $$S$$ with an interval $$R\_j$$that 

* overlaps with $$R\_i$$(correctness) 
* has a later end time (optimality)  

We can keep an interval $$R\_k$$ in the list if $$start\_time\_k$$ does not overlap from before (correctness).  

For example, we have an optimal removing set $$S\_1 = \[R\_1, R\_2, R\_7]$$. We can swap $$R\_7$$ with $$R\_3$$ to guarantee optimality because $$R\_3$$ overlaps $$R\_7$$ and ends at a later time. Again, we can swap $$R\_2$$ with $$R\_4$$ with the same reason. Now we have with a new removing set $$S\_2 = \[R\_1, R\_3, R\_4]$$ that is also optimal. Because we start this exchange process with a greedy choice, this greedy algorithm is proved to be optimal by induction. 

## Code 

```python
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    # sort by start time
    sorted_intvs = sorted(intervals, key=lambda intv: intv[0])

    removed = 0
    last_start_time = -5 * 10**4
    last_end_time = -5 * 10**4

    for intv in sorted_intvs:
        start_time, end_time = intv
        # non overlap
        if start_time >= last_end_time:
            last_start_time = start_time
            last_end_time = end_time
        else:
            # overlap
            removed += 1
            # greedily remove the interval with the latest end time
            if end_time < last_end_time:
                last_end_time = end_time

    return removed
```

## Complexity&#x20;

Time `O(nlogn) + O(n)` Space `O(n)`&#x20;

## Corollary&#x20;

This is actually a classic problem in interval scheduling. An equivalent problem statement is to find the maximum number of intervals that are non-overlapping.&#x20;

## Reading&#x20;

* Wikipedia - [Interval Scheduling](https://en.wikipedia.org/wiki/Interval_scheduling)&#x20;
* Algorithm Design - [Interval Scheduling](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf)&#x20;