> 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. 

![](/files/fH1bqvo5ISuTLINLuQQ3)

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;


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/greedy_algorithm/non-overlapping-intervals.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.