Count Ways to Group Overlapping Ranges
Real-world version: Splitting Overlapping Spans Into Two SetsThe statement here is our own: the same inputs, outputs and technique.
Spans are given as spans, where spans[i] = [from, to] covers every whole number from from up to to, both ends included. Two spans overlap when some whole number lies in both.
Put every span into one of two sets, called the first and the second, so that no number lies in a span of the first set and also in a span of the second. Either set may be left empty.
Return how many ways there are to do it, given as the remainder after dividing by 1000000007.
Examples
Example 1
- Input
- spans = [[1, 2], [3, 4]]
- Output
- 4
The two spans share no number, so each may go into either set freely, which is four ways.
Example 2
- Input
- spans = [[1, 5], [2, 3]]
- Output
- 2
The second span lies inside the first, so both must go into the same set, and that set may be either of the two.
Example 3
- Input
- spans = [[0, 0]]
- Output
- 2
A single span may go into either set.
Constraints
- 1 <= spans.length <= 10^5
- spans[i].length == 2
- 0 <= spans[i][0] <= spans[i][1] <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def count_ways(spans: list[list[int]]) -> int:public int countWays(int[][] spans)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's