Fewest Removals to Unclash
Problem
You are given a list of spans, each written as a start and an end, where the end is always larger than the start. Two spans clash when one begins strictly before the other finishes; touching at a single point is fine. Remove as few spans as possible so that nothing left clashes, and return how many you removed.
Examples
Input: spans = [(1, 2), (2, 3), (3, 4), (1, 3)]
Output: 1
Why: dropping (1, 3) leaves three spans that only touch at their endsInput: spans = [(1, 2), (1, 2), (1, 2)]
Output: 2
Why: three identical spans all clash, so only one can surviveInput: spans = [(1, 2), (2, 3)]
Output: 0
Why: edge case, touching at a point is not a clash so nothing is removedHints
0 / 3
Removing as few as possible is the same question as keeping as many as possible. Flip it and the problem gets easier to reason about.
Something about each span decides how much of the timeline it costs you. Duration and start time both mislead here; think about what it leaves behind.
Sort by finishing time and walk the list once, keeping a span whenever it starts at or after the last kept span's end. The answer is the total minus the number kept.
Solution
Maximising the kept spans is the classic interval-scheduling greedy, and the removals fall out as the leftover. Sorting by end time makes the first survivor the one that frees the timeline soonest, and an exchange argument shows swapping it into any optimal set never makes that set worse. One linear pass then keeps every span whose start clears the last kept end. Time is O(n log n) for the sort plus O(n) for the walk, and space is O(1) beyond the sort.
def fewest_removals(spans):
spans.sort(key=lambda s: s[1]) # earliest finishing first
kept, last_end = 0, float("-inf")
for s, e in spans:
if s >= last_end: # fits after everything kept so far
kept += 1
last_end = e
return len(spans) - kept
print(fewest_removals([(1, 2), (2, 3), (3, 4), (1, 3)])) # -> 1
print(fewest_removals([(1, 2), (1, 2), (1, 2)])) # -> 2
print(fewest_removals([(1, 2), (2, 3)])) # -> 0Stuck on the idea rather than the code? Interval Scheduling covers it.