Связанные компоненты в объединении сегментов - PullRequest
Новая
       62

Связанные компоненты в объединении сегментов

1 голос
/ 23 февраля 2020

У меня есть N сегментов (1 ≤ N ≤ 10 ^ 5) на 1-й числовой линии. Каждый сегмент содержит все вещественные числа 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 подмножеств!). Может ли кто-нибудь дать мне подсказку или указать мне sh в правильном направлении?

1 Ответ

2 голосов
/ 23 февраля 2020

Я предполагаю, что вы знакомы со стандартным алгоритмом линии развертки для подсчета подключенных компонентов заданного подмножества.

Идея состоит в том, чтобы по существу охватить все 2**n подмножества одновременно. После того, как мы рассмотрели s начальные события и e конечные события, есть 2**(e+n-s) подмножеств, где точка развертки не принадлежит объединению. На начальном событии мы добавляем этот счет к общей сложности.

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