DSA Non-Overlapping Intervals

The problem

Non-Overlapping Intervals asks how few intervals must be removed so the rest never overlap. An interval is a pair holding a start and an end. Intervals that touch at an endpoint do not overlap.

The answer in this article is the removal count, with the kept list shown beside it. Removing fewer is better. Keeping the most intervals and removing the fewest are the same goal stated twice.

cases = [[[1, 2], [2, 3], [3, 4], [1, 3]], [[1, 2], [1, 2], [1, 2]], [[1, 100], [11, 22], [1, 11], [2, 12]]]
for intervals in cases:
    print('intervals:', intervals)

The first case needs one removal. The second needs two, because only one copy of a repeated interval can stay. The third needs two, and its long interval is the one a careless rule would keep.

Intuition: keep the earliest start

The first idea keeps intervals in start order. It takes the earliest start first. That interval can run very long, and it can block several shorter intervals behind it.

The trap is one long interval that starts before all the others. It blocks every shorter interval behind it. Keeping it leaves a kept count of one, while removing it keeps three.

intervals = [[0, 10], [1, 3], [4, 6], [7, 9]]
by_start = sorted(intervals)
print('earliest start:', by_start[0])
blocked = [iv for iv in intervals if iv != by_start[0] and iv[0] < by_start[0][1]]
print('intervals it overlaps:', blocked)
print('kept if it stays: 1')
print('kept if it goes: 3')

Start order protects the worst interval in this set. Finish order does the opposite. The interval that ends first can block the least, and that fact drives the optimal rule. The third case at the start of the article has the same shape, with the interval from 1 to 100 in the long role.

Brute force: find the largest set that never overlaps

The brute force tests subsets from largest to smallest. The first subset with no overlaps gives the largest kept count. The removal count is the total minus that kept count.

import itertools
def brute(intervals):
    tested = [0]
    n = len(intervals)
    for size in range(n, -1, -1):
        for combo in itertools.combinations(intervals, size):
            tested[0] += 1
            ordered = sorted(combo)
            ok = True
            for i in range(1, len(ordered)):
                if ordered[i][0] < ordered[i - 1][1]:
                    ok = False
            if ok:
                return n - size, tested[0]
    return n, tested[0]
removed, tested = brute([[1, 100], [11, 22], [1, 11], [2, 12]])
print('removed:', removed)
print('subsets tested:', tested)

The brute force confirms two removals for the trap case. Its subset count doubles with each added interval. The greedy scan reaches the same count in one pass after a sort.

The optimal solution: keep the earliest finish, count the rest as removed

An interval is kept when its start is not before the end of the last kept interval, scanning in end order, and every other interval is counted as removed. That one sentence is the whole method.

A kept interval with an early end leaves the most room for the rest. That is why keeping the earliest finishing intervals removes the fewest possible. The rule is the activity selection rule, with the removed set counted instead of the kept set.

def removals(intervals):
    kept = []
    removed = 0
    last_end = None
    checks = [0]
    for start, end in sorted(intervals, key=lambda item: item[1]):
        checks[0] += 1
        if last_end is None or start >= last_end:
            kept.append([start, end])
            last_end = end
        else:
            removed += 1
    return kept, removed, checks[0]
cases = [[[1, 2], [2, 3], [3, 4], [1, 3]], [[1, 2], [1, 2], [1, 2]], [[1, 100], [11, 22], [1, 11], [2, 12]]]
for intervals in cases:
    kept, removed, checks = removals(intervals)
    print('intervals:', len(intervals), 'checks:', checks)
    print('kept:', kept)
    print('removed:', removed)

Every case from the start of the article matches its stated count. The long interval in the third case is removed, not kept. Its early start earns it nothing under a finish-order scan.

Walkthrough: scanning the first case in end order

The walk visits the intervals sorted by end. The state is the end of the last kept interval. Each step prints keep or remove with that state in view.

intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
kept = []
last_end = None
removed = 0
for start, end in sorted(intervals, key=lambda item: item[1]):
    if last_end is None or start >= last_end:
        kept.append([start, end])
        last_end = end
        print('keep', [start, end])
    else:
        removed += 1
        print('remove', [start, end])
print('kept:', kept)
print('removed:', removed)

Only the interval from 1 to 3 is removed. It starts before the end of the interval kept just before it in end order. The kept three touch at endpoints and never overlap.

Complexity

Sorting by end costs O(n log n) for n intervals. The scan is one pass, so its time is O(n) and its extra space is O(1) beyond the kept list.

for n in [4, 10, 20]:
    print('intervals', n, '- greedy checks:', n, ' brute subsets:', 2 ** n)

At 20 intervals the scan makes 20 checks against over a million subsets. The counts state the whole argument. No clock is needed to see the gap.

Edge cases and pitfalls

Counting a touching pair as an overlap is the classic mistake. An interval starting exactly at the last kept end is kept. A strict test would remove it and inflate the count on chain-like inputs.

An empty list needs no removals. A list with no overlaps also needs none, whatever order the intervals arrive in, because the sort runs before the scan.

def removals(intervals):
    kept_end = None
    removed = 0
    kept = 0
    for start, end in sorted(intervals, key=lambda item: item[1]):
        if kept_end is None or start >= kept_end:
            kept_end = end
            kept += 1
        else:
            removed += 1
    return kept, removed
print('empty:', removals([]))
print('touching chain:', removals([[1, 2], [2, 3]]))
print('identical pair:', removals([[1, 2], [1, 2]]))
print('trap case:', removals([[1, 100], [11, 22], [1, 11], [2, 12]]))

The touching chain keeps both intervals and removes none. The identical pair keeps one and removes one. Both answers come from the same start-at-or-after test.