Non-overlapping Intervals

Q: What is the time complexity of Non-overlapping Intervals?

The greedy solution sorts by end in O(n log n) and walks the intervals once, so the total is O(n log n) with O(n) space for the sorted copy. The dynamic programming version is O(n²) , and trying every set to keep is O(2^n) .

MediumIntervals Greedy

+10

Interval i runs from starts[i] to ends[i]. Return the smallest number of intervals you must remove so that no two of the rest overlap. Two intervals that only touch, where one ends at the exact point the other starts, do not overlap.

Function

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: the start of each interval
endsinteger-array: the end of each interval, at the same index as its start
Returnsinteger: the fewest intervals to remove so that the rest do not overlap

Constraints

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
The intervals are not sorted. Two intervals may be identical.

Examples

Input: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Output: 2
Explanation: In start order the intervals are [1,4], [2,3], [3,6] and [5,7]. Keep [2,3] and [3,6], which only touch, and remove the other 2. Three cannot stay: [1,4] overlaps [2,3], and [3,6] overlaps [5,7].

Input: starts = [0, 0, 0]ends = [5, 5, 5]
Output: 2
Explanation: All three intervals are [0,5], so any two overlap. One stays and you remove 2.

Input: starts = [4, 1, 2]ends = [6, 2, 4]
Output: 0
Explanation: [1,2], [2,4] and [4,6] meet end to start and never overlap, so you remove nothing and the answer is 0.

Follow-up

Suppose every interval has a value and you want the largest total value among intervals that do not overlap. Does keeping the interval that ends first still work?

Solution

Removing the fewest intervals is the same as keeping the most intervals that do not overlap: the answer is n minus that count. One greedy rule finds the count in O(n log n): of the intervals that still fit, always keep the one that ends first.

Keep or remove each interval

Correct, but does not finish on the largest tests

Intuition

Sort the intervals by start and decide for each one whether to keep or remove it. You may keep it only if it starts at or after the end of the last kept interval, so the kept intervals form a chain with no overlaps. Try both choices at every interval and take the larger count; the answer is n minus it.

Each interval can double the branches, so n intervals lead to up to 2^n paths. Thirty intervals that do not overlap already mean over a billion calls, and n goes up to 5000.

Algorithm

Sort the intervals by start, keeping each start with its own end.
Define mostKept(i, last): the most intervals you can keep from position i on, when last is the latest kept interval (-1 for none).
Past the end, return 0. Otherwise take mostKept(i+1, last), which removes interval i.
If interval i starts at or after the end of last, also try 1 + mostKept(i+1, i) and keep the larger.
Return n minus mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Longest chain with dynamic programming

Correct, but does not finish on the largest tests

Intuition

The search keeps asking the same question: how long is the longest chain that ends with this interval? Answer it once per interval. Sort by start and let chain[i] be the most intervals you can keep with interval i last.

An interval that can come right before i ends at or before starts[i], so it starts earlier and sits earlier in the sorted order. That gives chain[i] = 1 + chain[j] for the best such j, or 1 if none fits. In the first example the values are 1, 1, 2 and 2, so you keep 2 and remove 2.

The double loop makes n(n-1)/2 checks: about 12.5 million at n = 5000.

Algorithm

Sort the intervals by start, keeping each start with its own end.
Set chain[i] = 1 for every interval.
For each i and each j < i with ends[j] ≤ starts[i], set chain[i] to chain[j]+1 when that is larger.
Return n minus the largest value in chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Greedy: keep the interval that ends first

Intuition

Take the interval with the smallest end. Some best answer keeps it: in any largest set you can keep, swap the earliest interval for this one. It ends no later, so it still ends at or before the next kept interval starts, and the set keeps its size with no overlaps. Every interval that starts before its end overlaps it and must go, and what is left is the same problem on the intervals that start at or after that end.

In the first example, sorted by end, you keep [2,3], remove [1,4], keep [3,6] and remove [5,7]. Keeping the shortest interval instead fails on [1,5], [4,7], [6,10]: [4,7] overlaps both others and costs two removals where one is enough.

The sort costs O(n log n) and the walk O(n).

Algorithm

Sort the intervals by end, keeping each end with its own start.
Keep the first interval: set lastEnd to its end and removed to 0.
For each following interval, if it starts at or after lastEnd, keep it and set lastEnd to its end.
Otherwise add 1 to removed.
Return removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Pitfalls and edge cases

Treating touching intervals as overlapping. With start > lastEnd instead of start ≥ lastEnd, the chain [1,2], [2,4], [4,6] gives 1 instead of 0.
Sorting by start and keeping the earlier interval on an overlap. A wide [0,100] then pushes out [1,2], [3,4] and [5,6]: three removals instead of one.
Comparing each interval with its neighbor in the sorted list instead of the last kept interval. In the first example, [3,6] must be checked against the end of [2,3], not of the removed [1,4], or the answer comes out 3.
Sorting starts and ends as two separate lists. Each end has to stay with its own start.
Returning how many intervals you keep instead of how many you remove.

Frequently asked questions3

What is the time complexity of Non-overlapping Intervals?

The greedy solution sorts by end in O(n log n) and walks the intervals once, so the total is O(n log n) with O(n) space for the sorted copy. The dynamic programming version is O(n²), and trying every set to keep is O(2^n).

Can you sort by start time instead?

Yes, with a different rule on overlap. Walk the intervals by start, and when the next one overlaps the last kept interval, count one removal and keep whichever of the two ends first. It gives the same count in the same O(n log n) time.

Is Non-overlapping Intervals the same as the activity selection problem?

It is the other side of it. Activity selection asks for the most intervals that do not overlap; this problem asks for the fewest to remove, which is n minus that number. The same greedy rule, keep the activity that ends first, solves both.

def eraseOverlapIntervals(starts, ends):
    # Write code here

Test #1

Test #2

Test #3

Arguments

starts = [3, 1, 5, 2]
ends = [6, 4, 7, 3]

Expected Output

Non-overlapping Intervals

Function

Constraints

Examples

Hints

Solution

Keep or remove each interval

Longest chain with dynamic programming

Greedy: keep the interval that ends first

Pitfalls and edge cases

Frequently asked questions3

Similar problems