Non-overlapping Intervals

Question (LC.435)

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.

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

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

Time O(nlogn) + O(n) Space O(n)

Corollary

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.

Reading

• Wikipedia - Interval Scheduling
• Algorithm Design - Interval Scheduling