Scal zakresy w przedziałach

Question

Biorąc zestaw interwałów: {1-4, 6-7, 10-12} dodaj nowy interwał: (9,11), aby ostateczne rozwiązanie zostało "scalone": Wynik: {1 -4, 6-7, 9-12}. Połączenie może nastąpić po obu stronach (zarówno niskie, jak i wysokie).

Zobaczyłem, że na to pytanie udzielono odpowiedzi w wielu miejscach, ktoś nawet zasugerował użycie Trybu interwałowego, ale nie wyjaśnił, jak dokładnie by to wykorzystali. Jedyne znane mi rozwiązanie to uporządkowanie interwałów w porządku rosnącym ich czasu rozpoczęcia i powtarzanie ich i próba ich odpowiedniego scalenia.

Jeśli ktoś może mi pomóc zrozumieć, w jaki sposób możemy używać drzewek interwałowych w tym przypadku, to będzie świetnie!

[śledzę drzewo przedziałowe w CLR książki, ale nie rozmawiają o fuzji, wszyscy mówią o to wstawiania i wyszukiwania.]

Answer 1

(jestem zakładając, że środki interwały te nigdy nie mogą się pokrywać, ponieważ w przeciwnym razie zostaną scalone).

Jeden sposób na zrobienie tego byłoby przechowywać zrównoważone drzewa wyszukiwania binarnego z jednym węzłem na punkt końcowy zakresu. Każdy węzeł byłby wówczas oznaczany jako "otwarty" węzeł oznaczający początek przedziału lub "zamknięty" węzeł oznaczający koniec przedziału.

Wkładając nową linię, jeden z dwóch przypadków nastąpi w odniesieniu do punktu początkowego zakresu:

1. To już wewnątrz zakresu, co oznacza, że ​​można rozszerzyć już istniejący asortyment w ramach wstawienie.
2. Nie ma w zasięgu, więc utworzysz nowy "otwarty" węzeł.

Aby ustalić, w którym to momencie znajdujesz się, możesz wykonać poprzednie wyszukiwanie w drzewie, aby uzyskać punkt początkowy zakresu. Jeśli otrzymasz wartość NULL lub węzeł zamykający, musisz wstawić nowy otwarty węzeł reprezentujący punkt początkowy zakresu. Jeśli otrzymasz otwarty węzeł, po prostu będziesz przedłużać ten interwał.

Stamtąd należy określić, jak daleko zasięg sięga. Aby to zrobić, stale obliczyć następcę początkowego węzła włożonej dopóki jedna z poniższych sytuacji:

1. obejrzeniu wszystkich węzłów w drzewie. W takim przypadku musisz wstawić węzeł zamykający oznaczający koniec tego odstępu.

2. Po zamknięciu zakresu widzisz zamknięty węzeł. W takim przypadku znajdujesz się w środku istniejącego zasięgu, gdy kończy się nowy zakres, więc nie musisz robić nic więcej. Jesteś skończony.

3. Widzisz zamknięty lub otwarty węzeł przed końcem zakresu. W takim przypadku musisz usunąć ten węzeł z drzewa, ponieważ stary zakres jest podliczony przez nowy.

4. Widzisz otwarty węzeł po końcu zakresu. W takim przypadku wstaw nowy węzeł do drzewa, ponieważ musisz zakończyć bieżący zakres przed zobaczeniem początku nowego.

Zaimplementowane naiwnie, środowisko wykonawcze tego algorytmu wynosi O (log n + k log n), gdzie n oznacza liczbę interwałów i K jest liczbą przedziałów usuniętych w trakcie tego procesu (ponieważ trzeba zrobić n kasuje). Można jednak przyspieszyć to do O (log n), stosując następującą lewę. Ponieważ proces usuwania zawsze usuwa węzły w sekwencji, można użyć wyszukiwania następczego dla punktu końcowego, aby określić koniec zakresu do usunięcia. Następnie można spliczyć podzakres, aby usunąć go z drzewa, wykonując dwie operacje podziału drzewa i jedną operację łączenia drzew. Na odpowiednim zbalansowanym drzewie (na przykład czerwono-czarna lub gra) można to zrobić w łącznym czasie O (log n), który jest znacznie szybszy, jeśli wiele zakresów zostanie podliczonych.

Mam nadzieję, że to pomoże!

Answer 2

to sprawdzić. To może pomóc: - http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

Biblioteka oferuje następujące funkcjonalności:

1) interval_set

2) separate_interval_set

3) split_interval_set

Answer 3

Jest to po prostu robione przez dodanie interwału do końca zestawu przedziałów, a następnie wykonanie scalenia wszystkich elementów zestawu interwałów.

operacji scalania jest dobrze wyszczególnione tutaj: http://www.geeksforgeeks.org/merging-intervals/

Jeśli nie jesteś w nastroju do kodu C++, jest tu te same rzeczy w Pythonie:

def mergeIntervals(self, intervalSet): 
    # interval set is an array. 
    # each interval is a dict w/ keys: startTime, endTime. 
    # algorithm from: http://www.geeksforgeeks.org/merging-intervals/ 
    import copy 
    intArray = copy.copy(intervalSet) 
    if len(intArray) <= 1: 
     return intArray 
    intArray.sort(key=lambda x: x.get('startTime')) 
    print "sorted array: %s" % (intArray) 
    myStack = [] #append and pop. 
    myStack.append(intArray[0]) 
    for i in range(1, len(intArray)): 
     top = myStack[0] 
     # if current interval NOT overlapping with stack top, push it on. 
     if (top['endTime'] < intArray[i]['startTime']): 
      myStack.append(intArray[i]) 
     # otherwise, if end of current is more, update top's endTime 
     elif (top['endTime'] < intArray[i]['endTime']): 
      top['endTime'] = intArray[i]['endTime'] 
      myStack.pop() 
      myStack.append(top) 

    print "merged array: %s" % (myStack) 
    return myStack 

nie zapomnij nosetests aby potwierdzić, że masz prawo faktycznie działa:

class TestMyStuff(unittest.TestCase): 

    def test_mergeIntervals(self): 
     t = [ { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [ { 'startTime' : 11, 'endTime' : 15 }, { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 44, 'endTime' : 46 }, { 'startTime' : 72, 'endTime' : 76 } ] 

     t = [ { 'startTime' : 33, 'endTime' : 36 }, { 'startTime' : 11, 'endTime' : 35 }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46 } ] 
     mgs = MyClassWithMergeIntervalsMethod() 
     res = mgs.mergeIntervals(t) 
     assert res == [{'endTime': 36, 'startTime': 11}, {'endTime': 46, 'startTime': 44}, {'endTime': 76, 'startTime': 72}] 

Answer 4

klasy MergeIntervals publiczne {

public static class Interval { 

    public double start; 
    public double end; 

    public Interval(double start, double end){ 
     this.start = start; 
     this.end = end; 
    } 
} 

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){ 

    List<Interval> merge = new ArrayList<>(); 

    for (Interval current : nonOverlapInt){ 

     if(current.end < another.start || another.end < current.start){ 
      merge.add(current); 
     } 
     else{ 

      another.start = current.start < another.start ? current.start : another.start ; 
      another.end = current.end < another.end ? another.end : current.end;     
     }   
    } 
    merge.add(another); 
    return merge; 
} 

Answer 5

C#

public class Interval 
{ 
    public Interval(int start, int end) { this.start = start; this.end = end; } 
    public int start; 
    public int end; 
} 

void AddInterval(List<Interval> list, Interval interval) 
{ 
    int lo = 0; 
    int hi = 0; 
    for (lo = 0; lo < list.Count; lo++) 
    { 
     if (interval.start < list[lo].start) 
     { 
      list.Insert(lo, interval); 
      hi++; 
      break; 
     } 
     if (interval.start >= list[lo].start && interval.start <= list[lo].end) 
     { 
      break; 
     } 
    } 
    if (lo == list.Count) 
    { 
     list.Add(interval); 
     return; 
    } 

    for (hi = hi + lo; hi < list.Count; hi++) 
    { 
     if (interval.end < list[hi].start) 
     { 
      hi--; 
      break; 
     } 
     if (interval.end >= list[hi].start && interval.end <= list[hi].end) 
     { 
      break; 
     } 
    } 
    if (hi == list.Count) 
    { 
     hi = list.Count - 1; 
    } 

    list[lo].start = Math.Min(interval.start, list[lo].start); 
    list[lo].end = Math.Max(interval.end, list[hi].end); 

    if (hi - lo > 0) 
    { 
     list.RemoveRange(lo + 1, hi - lo); 
    } 
}