wyszukiwanie przedziału czasowego na liście interwałów?

Question

Powiedz, że [a, b] reprezentuje przedział na linii rzeczywistej od a do b, < b, włącznie (tj. [A, b] = zbiór wszystkich x takich, że < = x < = b). Powiedz też, że [a, b] i [c, d] "nakładają się", jeśli dzielą dowolne x tak, że x jest w obu [a, b] i [c, d].

Biorąc pod uwagę listę interwałów, ([x1, y1], [x2, y2], ...), jaki jest najskuteczniejszy sposób na znalezienie wszystkich takich interwałów, które pokrywają się z [x, y]?

Oczywiście, mogę wypróbować każdy i uzyskać go w O (n). Ale zastanawiałem się, czy mógłbym uporządkować listę interwałów w jakiś sprytny sposób, mógłbym znaleźć/jeden/nakładający się element w O (log N) za pomocą wyszukiwania binarnego, a następnie "rozejrzeć się" od tej pozycji na liście, aby znaleźć wszystkie nakładające się interwały. Jak jednak posortować interwały, aby taka strategia działała?

Należy zauważyć, że niektóre elementy w elementach listy mogą się pokrywać, co powoduje, że jest to trudne.

Próbowałem tego, sortując interwały po ich lewym końcu, prawym końcu, środku, ale żaden nie wydaje się prowadzić do wyczerpujących poszukiwań.

Pomoc?

Answer 1

[a, b] zachodzi na [x, y] iff b> x oraz < y. Sortowanie interwałów według ich pierwszych elementów daje interwały pasujące do pierwszego warunku w czasie logowania. Sortowanie interwałów według ich ostatnich elementów daje interwały pasujące do drugiego warunku w czasie logowania. Weź skrzyżowania wynikowych zestawów.

Answer 2

Po prostu szybka myśl "z mankietu", że tak powiem.

Czy można uporządkować je na 2 listy, jedną na początek interwałów, a drugą na koniec interwałów.

W ten sposób można porównać y z pozycjami na początku listy interwałów (np. Przez wyszukiwanie binarne), aby zmniejszyć liczbę kandydatów na podstawie tego.

Następnie można porównać x do pozycji na końcu listy interwałów.

EDIT

koperty: Jednorazowo

Jeśli porównujesz tylko jeden przedział do listy odstępach w jednorazowych sytuacji, nie wierzę sortowania wam pomóc since ideal sorting is O(n).

Wykonując liniowe przeszukiwanie wszystkich x, aby wyrównać wszelkie niemożliwe przedziały, a następnie wykonując kolejne liniowe przeszukiwanie pozostałych wierszy, można zmniejszyć całkowitą pracę. Chociaż nadal jest to O (n), bez tego robilibyśmy porównania 2n, podczas gdy przeciętnie robilibyśmy tylko (3n-1)/2 porównania w ten sposób.

Uważam, że jest to najlepsze rozwiązanie dla nieposortowanej listy.

koperty: Wstępne sortowanie nie liczy

W przypadku, gdy będziesz wielokrotnie porównywano pojedyncze odstępy do tej listy odstępach czasu i swojej wstępnego sortowania listy, można osiągnąć lepsze wyniki. Powyższy proces nadal obowiązuje, ale wykonując binarne przeszukiwanie na pierwszej liście, a następnie drugi można uzyskać O (m log n) w przeciwieństwie do O (mn), gdzie m jest liczbą porównywanych pojedynczych przedziałów. Uwaga, nadal daje ci to przewagę zmniejszania łącznych porównań. [2m log n w porównaniu do m (3 (log n) - 1)/2]

Answer 3

Można sortować za pomocą obu lewych i prawych końców w tym samym czasie i użyć obu list, aby wyeliminować brak zachodzących na siebie wartości.Jeśli lista zostanie posortowana według lewego końca, żaden z przedziałów po prawej stronie prawego końca zakresu testowego nie może się pokrywać. Jeśli lista zostanie posortowana według prawego końca, żaden z przedziałów po lewej stronie lewego końca zakresu testowego nie może się pokrywać.

Na przykład jeśli odstępy są

[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5] 

i jesteś znalezienie nakładania z [3,4] następnie sortując lewym końcu i pozycję prawego końca testu znakowania (z prawej strony jak tylko przewyższają wartość tak że 4 jest zawarty w przedziale)

[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7] 

wiesz [5,7] nie mogą zachodzić na siebie, a następnie sortując prawej strony i pozycję lewego końca testu znakowania

[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8] 

wiesz [1,2] i [2,2.5] nie mogą się pokrywać

Nie wiem, jak to będzie skuteczne, ponieważ masz do zrobienia dwa rodzaje i wyszukiwania.

Answer 4

A 'quadtree' to struktura danych często używana do poprawy wydajności wykrywania kolizji w 2 wymiarach.

Myślę, że możesz wymyślić podobną strukturę 1-d. Wymagałoby to pewnych wstępnych obliczeń, ale powinno skutkować wydajnością O (log N).

Zasadniczo zaczynasz od głównego "węzła", który obejmuje wszystkie możliwe interwały, a podczas dodawania węzła do drzewa decydujesz, czy znajduje się on po lewej, czy po prawej stronie punktu środkowego. Jeśli przekroczy punkt środkowy, dzieli się go na dwa przedziały (ale zapisuje oryginalnego rodzica) i rekurencyjnie kontynuuje od tego punktu. Możesz ustawić limit głębokości drzewa, co może zaoszczędzić pamięć i poprawić wydajność, ale dzieje się to kosztem trochę komplikacji (musisz przechowywać listę interwałów w swoich węzłach).

Następnie podczas sprawdzania przedziału, w zasadzie znajdujesz wszystkie węzły liści, w które byłby wstawiony, gdyby został wstawiony, sprawdź częściowe odstępy w tych węzłach dla przecięcia, a następnie zgłoś interwał, który jest rejestrowany przeciwko nim jako "oryginał". ' rodzic.

Answer 5

Jak widać w innych odpowiedziach, większość algorytmów łączy się ze specjalną strukturą danych. Na przykład dla niesortowanej listy przedziałów jako dane wejściowe najlepiej jest uzyskać dane wejściowe O(n). (I zwykle łatwiej jest myśleć w kategoriach struktury danych, która dyktuje algorytm).

W tym przypadku Twoje pytanie nie jest kompletna:

• Czy biorąc pod uwagę całą listę lub to ty rzeczywiście ją tworzy?

• Czy musisz wykonać tylko jedno takie wyszukiwanie lub wiele z nich?

• Czy masz jakieś szacunki dotyczące operacji, które powinien obsługiwać i ich częstotliwości?

Na przykład, jeśli musisz wykonać tylko jedno takie wyszukiwanie, nie warto wcześniej sortować listy. Jeśli jest ich wiele, wówczas droższe sortowanie lub generowanie "kwadratu 1D" będzie amortyzowane.

Jednak byłoby to trudne do rozwiązania, ponieważ prosty quadtree (jak rozumiem) jest w stanie wykryć kolizję, ale nie jest w stanie utworzyć listy wszystkich segmentów, które nakładają się na dane wejściowe .

Jedną z prostych implementacji będzie lista uporządkowana (według współrzędnych), w której wszystkie końce segmentów są wstawiane z początkiem/końcem flagi i numerem segmentu. W ten sposób, parsując go (nadal O (n), ale wątpię, czy możesz go przyspieszyć, jeśli potrzebujesz również listy wszystkich segmentów, które się pokrywają) i zachować ścieżkę wszystkich otwartych segmentów, które nie zostały zamknięte w " punkty kontrolne".

Answer 6

Dla kompletności, chciałbym dodać, że istnieje dobrze znana struktura danych dla tego problemu, znana (niespodzianka, niespodzianka) jako interval tree. Jest to zasadniczo wzmocnione zrównoważone drzewo (czerwono-czarne, AVL, twój kilof), które przechowuje interwały posortowane według lewego (niskiego) punktu końcowego. Powiększenie polega na tym, że każdy węzeł przechowuje największy prawy (wysoki) punkt końcowy w swoim poddrzewie. To drzewo pozwala znaleźć wszystkie nakładające się interwały w czasie O (log n).

Opisano to w CLRS 14.3.