1091MediumArraySorting

Splitting Overlapping Spans Into Two Sets

Tracked in this browser only

Trains the technique from

LeetCode 2580Count Ways to Group Overlapping Ranges

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def count_ways(spans: list[list[int]]) -> int:

Java

public int countWays(int[][] spans)

The intended approach

Time O(n log n) for the sort, then one pass.Space O(n) for the sorted spans.

Two spans that overlap have to land in the same set, and so do two spans joined by a chain of overlaps. So the spans fall into clumps, where a clump is a run of spans held together by overlaps, and each clump goes wholly into one set or wholly into the other, freely and independently of the others. That makes the answer two raised to the number of clumps. Spans in different clumps never overlap, so no choice can clash with another. Finding the clumps is a sweep. Sort the spans by where they start, then walk them keeping how far the current clump reaches. A span starting no later than that reach joins the clump and may push the reach further out; a span starting past the reach opens a fresh clump. Sorting by start is what makes one pass enough, since a later span can never reach back behind an earlier one's start. The power of two is taken to the remainder as it is built up.

Pythonentry point: count_ways

def count_ways(spans):
    mod = 1000000007
    order = sorted(spans, key=lambda span: (span[0], span[1]))
    clumps = 0
    reach = None
    for span in order:
        if reach is None or span[0] > reach:
            clumps += 1
            reach = span[1]
        elif span[1] > reach:
            reach = span[1]
    answer = 1
    for _ in range(clumps):
        answer = answer * 2 % mod
    return answer

The obvious version

Find the clumps by merging outright. Keep a group for each span and, for every pair of spans, merge their groups when the two spans share a number, following the parent chains up to each group's representative. Count the groups left and raise two to that. Costs every pair of spans rather than a sweep in sorted order.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_count_ways(spans):
    mod = 1000000007
    n = len(spans)
    parent = list(range(n))
    def top(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for i in range(n):
        for j in range(i + 1, n):
            low = spans[i][0] if spans[i][0] > spans[j][0] else spans[j][0]
            high = spans[i][1] if spans[i][1] < spans[j][1] else spans[j][1]
            if low <= high:
                a = top(i)
                b = top(j)
                if a != b:
                    parent[b] = a
    groups = set()
    for at in range(n):
        groups.add(top(at))
    answer = 1
    for _ in range(len(groups)):
        answer = answer * 2 % mod
    return answer

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in