Drop Spans Covered by Others
Problem
A monitoring system has a list of alert windows [start, end]. A window is redundant when another window in the list covers it completely, meaning the other one starts no later and ends no earlier. Remove every redundant window and return how many remain. No two windows in the list are identical.
Examples
Input: spans = [[1, 4], [3, 6], [2, 8]]
Output: 2
Why: [3, 6] lies inside [2, 8]; [1, 4] and [2, 8] only overlapInput: spans = [[1, 2], [1, 4], [3, 4]]
Output: 1
Why: [1, 4] covers both others, including the two that share an endpoint with itInput: spans = [[3, 5]]
Output: 1
Why: edge case, a lone window has nothing to cover itHints
0 / 3
Comparing every pair of windows works but costs quadratic time. Put the windows in an order where a covering window is always seen before the windows it covers.
Sort by start ascending, and for equal starts by end descending. Then any window that could cover the current one has already been seen.
Walk the sorted list keeping the furthest end seen so far. A window whose end does not pass that furthest end is covered by an earlier window; any other window is kept and pushes the furthest end forward.
Solution
After sorting by start ascending and, for ties, by end descending, every window that starts no later than the current one comes before it, and among windows with the same start the longest comes first. The current window is then covered exactly when some earlier window reaches at least as far, which is a single comparison against the furthest end seen so far. The tie-break matters: without it, [1, 2] would be seen before [1, 4] and wrongly kept. Time is O(n log n) for the sort and space is O(n) for the sorted copy.
def uncovered_count(spans):
spans = sorted(spans, key=lambda s: (s[0], -s[1])) # longer first on ties
kept, reach = 0, float("-inf")
for start, end in spans:
if end > reach: # nothing earlier covers it
kept += 1
reach = end
return kept
print(uncovered_count([[1, 4], [3, 6], [2, 8]])) # -> 2
print(uncovered_count([[1, 2], [1, 4], [3, 4]])) # -> 1
print(uncovered_count([[3, 5]])) # -> 1
print(uncovered_count([[1, 4], [2, 3]])) # -> 1Stuck on the idea rather than the code? Interval Basics & Sorting covers it.