Szukam dobrego sposobu spłaszczenia (podzielenia) listy potencjalnie nakładających się zakresów liczbowych. Problem jest bardzo podobny do pytania: Najszybszy sposób podziału nakładających się zakresów dat i wielu innych.
Jednak zakresy to nie tylko liczby całkowite i szukam porządnego algorytmu, który można łatwo zaimplementować w Javascript lub Python itp.
Przykładowe dane:
Przykładowe rozwiązanie:
Przepraszam, jeśli to duplikat, ale jeszcze nie znalazłem rozwiązania.
javascript
algorithms
python
Jollywatt
źródło
źródło
Odpowiedzi:
Chodź od lewej do prawej, używając stosu, aby śledzić, w jakim kolorze jesteś. Zamiast dyskretnej mapy użyj punktów 10 w zbiorze danych jako punktów przerwania.
Zaczynając od pustego stosu i ustawiając
start
na 0, zapętlaj aż do końca:start
, i wepchnij go i wszystkie kolory z niższej rangi na stos. Na spłaszczonej liście zaznacz początek tego koloru.start
i znajdź koniec bieżącego kolorustart
koniec tego koloru, zdejmij go ze stosu i sprawdź kolor o najwyższej pozycji w rankingustart
jest w zakresie następnego koloru, dodaj ten kolor do spłaszczonej listy, zaczynając odstart
.Oto mentalny przegląd danych przykładowych:
źródło
To rozwiązanie wydaje się najprostsze. (Lub przynajmniej najłatwiejszy do uchwycenia)
Potrzebna jest tylko funkcja odejmowania dwóch zakresów. Innymi słowy, coś, co da to:
Co jest dość proste. Następnie możesz po prostu iterować przez każdy z zakresów, zaczynając od najniższego, i dla każdego z nich odejmować po kolei wszystkie zakresy nad nim. I masz to.
Oto implementacja odejmera zakresu w Pythonie:
Korzystając z tej funkcji, resztę można wykonać w następujący sposób: („zakres” oznacza zakres, ponieważ „zakres” jest słowem kluczowym Python)
To daje
[['red', [12.5, 13.8]], ['blue', [0.0, 2.0]], ['green', [2.0, 3.5]], ['green', [10.0, 12.0]], ['yellow', [3.5, 6.7]], ['orange', [6.7, 10.0]]]
, co jest poprawne.źródło
Jeśli dane są naprawdę podobne do danych przykładowych, możesz utworzyć mapę w następujący sposób:
Następnie wystarczy przejść przez tę mapę, aby wygenerować zakresy
Aby działać, wartości muszą znajdować się w stosunkowo małym zakresie, tak jak w przykładowych danych.
Edycja: aby pracować z prawdziwymi liczbami zmiennoprzecinkowymi, użyj mapy do wygenerowania mapowania wysokiego poziomu, a następnie odwołaj się do oryginalnych danych, aby utworzyć granice.
źródło
Oto stosunkowo proste rozwiązanie w Scali. Przeniesienie do innego języka nie powinno być trudne.
apply
pobieraSet
wszystkie zakresy, które zostały już zastosowane, odnajduje nakładki, a następnie zwraca nowy zestaw minus nakładki oraz nowy zakres i nowo podzielone zakresy.foldLeft
wielokrotnie wywołujeapply
przy każdym zakresie wejściowym.źródło
Po prostu zachowaj zestaw zakresów posortowany według początku. Dodaj zakres obejmujący wszystko (-oo .. + oo). Aby dodać zakres r:
źródło