Remove covered ranges
Count the ranges left after removing every range that lies completely inside another range, by sorting on start and walking through with the farthest end seen. About 20 minutes.
Contained means no new reach
A range [c, d) covers [a, b) when c ≤ a and b ≤ d. You want to count the ranges that are not covered by any other.
Sort by start. Once sorted, any range that could cover the current one starts at or before it, so it comes earlier. Then a range is covered exactly when an earlier range reaches at least as far to the right.
The tie rule
Watch equal starts. Take [1, 4] and [1, 2]: the second is covered by the first. If the short one came first, it would look uncovered, since nothing before it reaches further.
So sort by start ascending and, for equal starts, by end descending. Then walk through keeping the farthest end: count a range only when its end is beyond it, and update the farthest end.
ranges.sort(key=lambda r: (r[0], -r[1])) # same start: the longer one first
[1, 5] ends at 5, beyond the farthest end 0. Keep it. Farthest 5.
Ranges [1, 5] and [1, 3] share a start. Which is covered?
- A[1, 3], by the longer range
- B[1, 5], by the shorter range
- CNeither is covered
Show the answer
[1, 3], by the longer range. Both start at 1 but [1, 5] reaches further.
Remove covered ranges
You are given ranges, each as [start, end). A range [c, d) covers a range [a, b) if c ≤ a and b ≤ d. Remove every range that is covered by another range, and return the number of ranges left.
ranges = [[1, 4], [3, 6], [2, 8]] → 2
0 ≤ ranges.length ≤ 100,000 · 0 ≤ start < end ≤ 100,000 · all ranges are distinct