Most Non-overlapping Intervals

01 · Question

Given closed intervals [start,end] with start < end, return the maximum number that can be selected without overlap. Touching endpoints overlap. Empty input returns zero.

Example: [[1,2],[2,3],[3,4]] returns 2, by selecting the first and last intervals.

02 · Analysis

Sort by end time and accept an interval when its start is strictly greater than the last accepted end. Replacing the first interval in an optimum with the earliest-finishing one cannot block any later choice, so repeat the argument on the remainder. Time O(n log(n+1)); this implementation copies the intervals before sorting, using O(n) space. Maximizing total weights is a different problem and is not solved by this rule.

03 · Solution

Reference solution

1def most_non_overlapping(intervals):
2    last_end = float('-inf')
3    count = 0
4    for start, end in sorted(intervals, key=lambda item: item[1]):
5        if start > last_end:
6            count += 1
7            last_end = end
8    return count

Gas Station