Obliczanie najmniejszej dodatniej liczby całkowitej nie objętej żadnym z przedziałów

Question

Ktoś wysłał to pytanie tutaj kilka tygodni temu, ale wyglądało to okropnie jak praca domowa bez wcześniejszych badań, a OP szybko usunął go po otrzymaniu kilku zniżek.

Samo pytanie było jednak dość ciekawe i zastanawiałem się nad tym przez tydzień bez znalezienia satysfakcjonującego rozwiązania. Mam nadzieję, że ktoś może pomóc?

Pytanie jest następujący: podano listę odstępach liczbę całkowitą, której granice mogą dowolne wartości z 0 do N³ znajdź najmniejszą liczbę całkowitą ii taki sposób, że nie należą do żadnej z tych przedziałach wejściowych.

Na przykład, jeśli poda się listę [3,5] [2,8] [0,3] [10,13] (N = 4), algorytm powinien powrócić 9.

Najprostszym rozwiązaniem, które można myślę tras w O(n log(n)) i składa się z trzech etapów:

1. Uporządkuj przerwach poprzez zwiększenie dolnej granicy
2. • Jeśli najmniejsza dolna granica wynosi> 0, return 0;
   • przeciwnym przypadku wielokrotnie połączyć pierwszy interwał z drugim, do pierwszego przedziału (powiedzmy [a, b]) nie dotyka drugiego (powiedzmy [c, d]) - to jest do b + 1 < C, lub aż do chwili tylko jeden przedział.
3. Powrót b + 1

To proste rozwiązanie działa w O(n log(n)), ale oryginalny plakat napisał, że algorytm powinien działać w O(n). To jest trywialne, jeśli przedziały są już posortowane, ale przykład podany przez PO zawiera nieposortowane interwały. Myślę, że to musi mieć coś wspólnego z N³ związany, ale nie jestem pewien, co ... Hashing? Liniowy podział czasu? Pomysły są mile widziane.

---

Tutaj jest szorstka implementacja Pythona dla algorytmu opisanego powyżej:

def merge(first, second): 
    (a, b), (c, d) = first, second 
    if c <= b + 1: 
     return (a, max(b, d)) 
    else: 
     return False 

def smallest_available_integer(intervals): 
    # Sort in reverse order so that push/pop operations are fast 
    intervals.sort(reverse = True) 

    if (intervals == [] or intervals[-1][0] > 0): 
     return 0 

    while len(intervals) > 1: 
     first = intervals.pop() 
     second = intervals.pop() 

     merged = merge(first, second) 
     if merged: 
      print("Merged", first, "with", second, " -> ", merged) 
      intervals.append(merged) 
     else: 
      print(first, "cannot be merged with", second) 
      return first[1] + 1 

print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)])) 

wyjściowa:

Merged (0, 3) with (2, 8) -> (0, 8) 
Merged (0, 8) with (3, 5) -> (0, 8) 
(0, 8) cannot be merged with (10, 13) 
9 

Answer 1

Rozwijając komentarzu @ mrip za: można to zrobić w czasie O (n) czas, używając dokładnego algorytmu, który opisałeś, ale zmieniając sposób działania algorytmu sortowania.

Zazwyczaj sortowanie radix używa zasady 2: elementy są podzielone na dwa różne segmenty w oparciu o to, czy ich bity to 0, czy 1. Każda runda sortowania radix zajmuje czas O (n), i jest jedna runda na bit największa liczba. Wywołanie tego największego nunbera U oznacza, że ​​złożoność czasu wynosi O (n log U).

Można jednak zmienić podstawę sortowania radix na inne bazy. Używając bazy b, każda runda wymaga czasu O (n + b), ponieważ potrzeba czasu O (b) do zainicjowania i iteracji nad wiaderkami i czasu O (n) w celu dystrybucji elementów do wiader.Następnie są rejestrowane rundy _b. Daje to czas działania dziennika O ((n + b) _b U).

Podejście polega na tym, że od maksymalnej liczby U = n można ustawić b = n i użyć sortowania radix base-n. Liczba rund jest teraz rejestrowana, a każda runda zajmuje czas O (n), więc całkowita liczba operacji do sortowania liczb wynosi O (n). Bardziej ogólnie, możesz sortować liczby w zakresie [0, n ^k) w czasie O (kn) dla dowolnego k. Jeśli k jest stałą stałą, jest to czas O (n).

W połączeniu z oryginalnym algorytmem rozwiązuje to problem w czasie O (n).

Mam nadzieję, że to pomoże!

Answer 2

Jakimś sposobem, należy wykorzystać uzupełnienie tych interwałów. Przypuśćmy, że C() daje ci dopełnienie dla przedziału, na przykład C ([3,5]) będzie liczbą całkowitą mniejszą niż 3 i większą niż 5. Jeśli maksymalną liczbą jest N^3, to używając modulo N^3 + 1 można nawet przedstawić jako kolejny przedział [6, (N^3 + 1) +2].

Jeśli chcesz numer, który nie należy do żadnego z oryginalnych przedziałów, ten sam numer powinien być obecny we wszystkich uzupełnieniach tych przedziałów. Następnie sprowadza się do napisania funkcji, która może obliczyć przecięcie dowolnych dwóch takich "przedziałów uzupełniających".

Nie zrealizowałem tego pomysłu, ponieważ moje rysunki piórem i papierem wskazywały, że przy obliczaniu takiego skrzyżowania było więcej przypadków, niż początkowo sądziłem. Ale myślę, że idea, która się za tym kryje, jest prawidłowa i spowodowałaby algorytm O (n).

EDIT

Na głębszego zastanowienia, nie jest najgorszy scenariusz, który sprawia, że ​​rzeczy bardziej skomplikowane, niż pierwotnie wyobrażał.