CODEWITHSUNDEEP
algorithmoptimizationlanguage-agnosticadhoc
cracra
cracra

Reputation: 107

Connected components in union of segments

I have N segments (1 ≤ N ≤ 10^5) on a 1D number line. Each segment contains all reals x such that starting point ≤ x ≤ ending point.

We can say that the "union" of a set of segments is the set of all x that are contained within at least one segment. The "complexity" of a set of segments is the number of connected regions represented in its union.

Over all 2^n subsets of the segments, we want to compute the sum of the complexities.

Example:

You have three segments, [1, 6], [2, 3], [4, 5] where in [a, b] a = starting point, b = ending point.

The solution is 8. Here are the complexities of each subset: [1,6]⟹1,[2,3]⟹1,[4,5]⟹1

{[1,6],[2,3]}⟹1,{[1,6],[4,5]}⟹1,{[2,3],[4,5]}⟹2

{[1,6],[2,3],[4,5]}⟹1

The answer is 1+1+1+1+1+2+1=8.

Clearly we cannot iterate over all subsets (2^N subsets!) Could anyone give me a hint or push me in the right direction?

Upvotes: 0

Views: 624

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

I'll assume you're familiar with the standard sweep-line algorithm for counting connected components of a given subset.

The idea is essentially to sweep over all 2**n subsets at the same time. After we've swept over s start events and e end events, there are 2**(e+n-s) subsets where the sweep point doesn't belong to the union. On a start event, then, we add this count to the total complexity.

In Python:

def total_complexity(segments):
    segments = list(segments)
    events = [(segment[i], i) for segment in segments for i in range(2)]
    events.sort()
    total = 0
    ended = 0
    not_started = len(segments)
    for t, is_end in events:
        if is_end:
            ended += 1
        else:
            not_started -= 1
            total += 2 ** (ended + not_started)
    return total


print(total_complexity([(1, 6), (2, 3), (4, 5)]))

Upvotes: 2

Related Questions