Algorytm wyzwanie: zakres dat łączenie

Question

Jestem stoi ciekawy problem:

• Mam kilka zakresów dat, które mogą się nakładać
• każdy z nich ma swoją nazwę

Czy jest możliwe zakresy "nakładających się" zakresów? Oznacza to, że do generowania:

• nowy zestaw zakresów gdzie żaden pokrywa pozostałe
• każdy z tej nowej serii ma listę nazwami

Może zrobię to nieco więcej graficzny. To co mam najpierw:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

To co chciałbym uzyskać:

|------|---------|-------|-----|-----| 
     a  a,c  a,b,c a,b b 

znalazłem rozwiązanie tego rodzaju prac, które jednak nie jest eleganckie:

1. Przekształcam każdy zakres (od, do) na listę dni (d1, d2, d3 itd.)
2. Nazwy grup według dnia
3. Łączę grupy, które zawierają te same nazwy, aby odtworzyć zakresy

Czy możesz wymyślić lepsze rozwiązanie? Pracuję z C#, ale każdy niezależny od języka pomysł byłby bardzo ceniony. Dzięki!

Answer 1

bym

1. Miej nieuporządkowaną listę „open” waha
2. Rozpocznij od dnia 1, a następnie dodaj pierwszy zakres do listy zakresów otwartym.
3. Przenieś do następnej granicy zakresu (rozpoczęcia lub zamknięcia). Utwórz swój pierwszy "wynikowy" zakres: od 1 dnia, kończący się tego dnia. W tym są pozycje na liście otwartych zakresów.
4. Jeśli napotkany zakres znajduje się już na liście otwartych zakresów, usuń go. W przeciwnym razie dodaj.
5. Powtórz 3 i 4, przesuwając wzdłuż linii.

Z całą pewnością nie udawało mi się tego wyjaśnić. Wkrótce napiszę o tym kod. Ale do tego czasu, oto co by się stało w roztworze:

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

 
1. Start at day 1, add A to open ranges list, which now contains [A] 
2. Move to the start of C. First RESULT RANGE: A range from Day 1 to C's start, 
     with a value A. (what is in your open ranges list) 
3. Add C to the open ranges list, which now contains [A,C] 
4. Move to the start of B. Second RESULT RANGE: A range from C's start to B's 
     start, with a value A,C. (what is in your open ranges list) 
5. Add B to the open ranges list, which now contains [A,C,B] 
6. Move to the end of C. Third RESULT RANGE: A range from B's start to C's end, 
     with a value of A,C,B. 
7. Remove C from the open ranges list, which now contains [A,B] 
8. Move to the end of A. Fourth RESULT RANGE: A range from C's end to A's end, 
     with a value of A,B 
9. Remove A from the open ranges list, which now contains [B] 
10. Move to the end of A. Fourth RESULT RANGE: A range from A's end to B's end, 
     with a value of B 

RESULT RANGES 
1. from Day 1 to C's start: A 
2. from C's start to B's start: A,C 
3. from B's start to C's end: A,C,B 
4. from C's end to A's end: A,B 
5. from A's end to B's end: B 

---

Alternatywna metoda

Można to zrobić:

1. Zachowaj uporządkowaną listę „zakresów wyjściowych ". Ułatwia to sprawdzenie, czy punkt znajduje się w pewnym zakresie, a także jakie zasięgi następują po sobie.
2. Skorzystaj z zakresu wejściowego.
3. Sprawdź, czy jest całkowicie przed lub całkowicie po wszystkich zakresach wyjściowych, i odpowiednio postępuj. Pomiń kolejne kroki i wróć do kroku 2, jeśli tak.
4. Porównaj punkt początkowy z zakresami wyjściowymi
5. Jeśli występuje przed jakimkolwiek innym zakresem wyjściowym, dodaj nowy zakres wyjściowy od początku do początku pierwszego zakresu wyjściowego.
6. Jeśli znajduje się pomiędzy już istniejącym zakresem wyjściowym, podziel ten zakres wyjściowy w tym punkcie. Pierwsza część będzie miała tych samych "rodziców", a druga część będzie miała tych samych rodziców + nowy zakres wejściowy.
7. Teraz porównaj jego punkt końcowy z zakresami wyjściowymi.
8. Jeśli występuje po jakimkolwiek innym zakresie wyjściowym, dodaj nowy zakres wyjściowy od końca ostatniego zakresu wyjściowego do jego końca.
9. Jeśli znajduje się pomiędzy już istniejącym zakresem wyjściowym, podziel ten zakres wyjściowy w tym punkcie. Druga część będzie miała tych samych "rodziców", a pierwsza część będzie miała tych samych rodziców + nowy zakres wejściowy
10. Dodaj bieżący zakres wejściowy jako część do wszystkich zakresów pomiędzy dwoma "przetworzonymi" zakresami w krokach 6 i 9, jeśli jakiekolwiek.
11. Powtórz 2-6 dla wszystkich zakresów wejściowych.

Oto kilka pierwszych kroków, za pomocą przykładowych danych + inny zakres D: ("przetworzone" zakresach wskazanych przez **double stars**)

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 
d  |------------------------| 

 

1. 
    Process A 
    Output ranges: |--------------A---------------| 
2. 
    Process B 
    - Start of B is in **A**; split A in two: 
        |-------A-------|------AB------| 
    - End of B is after any output range range; 
     creating new output range at end 
        |-------A-------|------AB------|---B---| 
    - Nothing was/is in between **A** and (nothing) 
3. 
    Process C 
    - Start of C is in **A**; split A in two: 
        |---A----|--AC--|------AB------|---B---| 
    - End of C is in **AB**; split AB in two: 
        |---A----|--AC--|--ABC--|--AB--|---B---| 
    - There were/are no ranges between **A** and **AB** 

4. 
    Process D 
    - Start of D is in **A**; split A in two: 
        |-A-|-AD-|--AC--|--ABC--|--AB--|---B---| 
    - End of D is in **AB**; split AB in two: 
        |-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---| 
    - Ranges AC and ABC were/are in between **A** and **AB** 
        |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Final output:  |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Answer 2

może chcesz mieć przyjrzeć Interval Trees .

Answer 3

Mogłabyś:

1. posortować listę wszystkich dat (łączenie zi do dat)
2. następnie wzdłuż tej liście, każda nowa seria będzie od jednego dnia do następnego początku lub na końcu data inna niż poprzednia.

Aby nazwać nowe zakresy, warto mieć listę oryginalnych nazw zakresów, które zawiera aktualny nowy zakres, a za każdym razem, gdy trafi się data zakończenia, usuń starą nazwę zakresu z listy, a każdego dnia, w którym trafiłeś datę rozpoczęcia, dodaj jego nazwę do listy.

Answer 4

Wykonaj:

Utwórz klasę Event.

class DateEvent : IComparable<DateEvent> 
{ 
    public Date Date; 
    public int DateRangeId; 
    public bool IsBegin; // is this the start of a range? 

    public int CompareTo(DateEvent other) 
    { 
     if (Date < other.Date) return -1; 
     if (Date > other.Date) return +1; 
     if (IsBegin && !other.IsBegin) return -1; 
     if (!IsBegin && other.IsBegin) return +1; 
     return 0; 
    } 
} 

Definiowanie List<DateEvent> events;

Dodaj datę rozpoczęcia i zakończenia każdego zakresu jest na listę:

for (int i = 0; i < dateRanges.Length; ++i) 
{ 
    DateRange r = dateRanges[i]; 
    events.Add(new DateEvent(r.BeginDate, i, true)); 
    events.Add(new DateEvent(r.EndDate, i, false)); 
} 

Sortuj wydarzenia.

events.Sort(); 

teraz założyć klasę wyjściowy:

class OutputDateRange 
{ 
    public Date BeginDate; 
    public Date EndDate; 
    public List<string> Names; 
} 

Wreszcie przemierzać zdarzenia, utrzymując, które obecne są w zakresie:

List<int> activeRanges; 
List<OutputDateRange> output; 
Date current = events[0].Date; 
int i = 0; 

while (i < events.Length;) 
{ 
    OutputDateRange out = new OutputDateRange(); 
    out.BeginDate = current; 

    // Find ending date for this sub-range. 
    while (i < events.Length && events[i].Date == current) 
    { 
     out.EndDate = events[i].Date; 
     if (events[i].IsBegin) 
      activeRanges.Add(events[i].DateRangeId); 
     else 
      activeRanges.Remove(events[i].DateRangeId); 
     ++i; 
    } 

    if (i < events.Length) 
     current = events[i].Date; 

    foreach (int j in activeRanges) 
     out.Names.Add(dateRanges[j].Name); 

    output.Add(out); 
} 

To powinno załatwić sprawę. Zauważ, że nie stworzyłem konstruktorów, a kod jest trochę brzydki, ale mam nadzieję, że przekazuje ogólny pomysł.

Answer 5

Mam kod, który to robi. Opiera się on na zestawie wejściowym zamawianym przez from, a następnie to (tj. Jeśli był to SQL, byłby to ORDER BY from_value, to_value), ale po tym jest całkiem optymalny.

Moja implementacja w zasadzie opisuje to, co opisuje @Justin L., więc jeśli chcesz tylko opis tekstowy, spójrz na jego odpowiedź na algorytm.

Kod jest tutaj: LVK.DataStructures i pliki, które chcesz, aby spojrzeć na to:

• Range.cs
• RangeExtensions.cs, w szczególności metoda plasterek na line 206 i dalszych.

Aby go użyć:

List<Range<DateTime>> ranges = ... 
var slices = ranges.Slice(); 

To daje jedną nową ofertą dla każdego segmentu, a dla każdej takiej zakresie trzeba właściwość .DATA zawierający referencje z powrotem do przyczyniających zakresach.

tj. w przypadku Twojego oryginalnego przykładu otrzymasz dokładnie to, co chcesz, poszczególne zakresy, z zakresami a, b, c itd. we właściwości .Data.

Klasy mogą korzystać z innych części mojej biblioteki klasowej, która już tam jest. Jeśli zdecydujesz się z niego skorzystać, po prostu skopiuj porcje, których chcesz użyć.

Jeśli interesuje Cię tylko implementacja, możesz ją znaleźć w pliku RangeExtensions.cs, line 447 i późniejszej w procedurze InternalSlice.

Answer 6

1. Mam listę pierwsze, nie wiem, jego długość, ale mam 3 znaków
2. czek na jednym gnieździe, jeśli A tam? dodać "A", jeśli B tam jest? dodać "B", jeśli jest c? dodaj „C”
3. udać się do innego gniazda, cykl jak # 2
4. końcowego, gdy nic nie dodaje do innego nowego gniazda
5. Mam listę
6. spłaszczyć listę o