Non Overlapping Removals

Problem

Given a list of intervals [start, finish], return the smallest number of them you must remove so that none of the survivors overlap. Intervals that only touch at an endpoint — one finishing exactly where the next starts — do not count as overlapping.

Examples

Input:  intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Why:    dropping [1, 3] leaves three intervals that only touch at endpoints

Input:  intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Why:    all three cover the same span, so only one can stay

Input:  intervals = []
Output: 0
Why:    edge case, nothing to remove

Hints

0 / 3

1. Hint 1reveal
2. Hint 2locked
3. Hint 3locked

def min_removals(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda p: p[1])        # earliest finisher first
    kept, end = 1, intervals[0][1]
    for start, finish in intervals[1:]:
        if start >= end:                      # touching is not overlapping
            kept += 1
            end = finish
    return len(intervals) - kept

print(min_removals([[1, 2], [2, 3], [3, 4], [1, 3]]))  # -> 1
print(min_removals([[1, 2], [1, 2], [1, 2]]))          # -> 2
print(min_removals([]))                                # -> 0