段并集的连接组件-解网

问：

我在一维数字线上有 N 段（1 ≤ N ≤ 10^5）。每个线段包含所有实数 x，使得起点 x ≤≤终点。

我们可以说，一组段的“并集”是包含在至少一个段中的所有 x 的集合。一组段的“复杂性”是其并集中表示的连接区域的数量。

在段的所有 2^n 个子集上，我们想要计算复杂度的总和。

例：

你有三个段，[1， 6]、[2， 3]、[4， 5]，其中 [a， b] a = 起点，b = 终点。

解决方案是 8。以下是每个子集的复杂性： [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

答案是1+1+1+1+1+2+1=8。

显然，我们不能遍历所有子集（2^N 个子集！谁能给我一个提示或推动我朝着正确的方向前进？

算法优化语言无关的 adhoc

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)]))

段并集的连接组件

Connected components in union of segments

评论

评论