Biorąc pod uwagę dowolną serię dat wejścia z pojedynczymstan Otwarty lub Zamknięty tak, aby co najmniej jedna data wejściowa (stan otwarty) skutkowała dodaniem pojedynczej daty (Zamknięta, data maksymalna) w celu uzupełnienia sekwencji wyjściowej, jakiego algorytmu użyłbyś do wygenerowania wyniku przestrzega następujących zasad?
1. Nie ma kolejnych otwartych dat ani kolejnych zamkniętych dat.
2. Dla każdej Daty otwartej jest dokładnie jedna data Zamknięta.
3. Pierwsza data powinna być otwarta, a ostatnia data powinna być zamknięta.
4. Poza pierwszą datą otwarcia i ostatnią datą zamknięcia każda data otwarcia powinna następować bezpośrednio po poprzedniej dacie zamknięcia lub inaczej, każda data zamknięcia powinna być dniem poprzedzającym następną datę otwarcia.
5. Data końcowa to data zamknięcia i maksymalna (9999-12-31, w tym przykładzie)
To nie jest zadanie domowe, zaimplementowałemto w języku C # i kod produkcyjny, który będzie wykonywany miliony razy. Wydajność jest ważna, tak, ale bardzo wtórna w stosunku do czytelności. Zastosowany algorytm działa doskonale, ale wygląda okropnie. Witamy w dowolnym języku. Przetłumaczę, jeśli to konieczne. Dzięki.
Przykład 1
input:
[2000-01-01,open]
output:
[2000-01-01,open]
[9999-12-31,closed]
Przykład 2
input:
[2000-01-01,open]
[2001-01-01,open]
output:
[2000-01-01,open]
[2000-12-31,closed]
[2001-01-01,open]
[9999-12-31,closed]
Przykład 3
input:
[2000-01-01,open]
[2004-04-30,closed]
output:
[2000-01-01,open]
[2004-04-30,closed]
[2004-05-01,open]
[9999-12-31,closed]
Przykład 4
input:
[2000-01-01,open]
[2000-03-17,open]
[2002-09-11,closed]
[2003-04-07,closed]
output:
[2000-01-01,open]
[2000-03-16,closed]
[2000-03-17,open]
[2002-09-11,closed]
[2002-09-12,open]
[2003-04-07,closed]
[2003-04-08,open]
[9999-12-31,closed]
Odważę się zapytać, która klasa języka najlepiej rozwiązuje ten problem?
Odpowiedzi:
5 dla odpowiedzi № 1- Sortuj dane wejściowe według daty.
- Iteruj przez wejście, śledząc bieżący stan.
- Jeśli stan jest otwarty i napotkano otwartą datę, wprowadź zamkniętą datę.
- Jeśli stan jest zamknięty i napotkana jest zamknięta data, wstaw datę otwarcia.
- Jeśli stan jest zamknięty i napotkana jest data otwarcia, która nie jest dniem następującym po poprzedniej zamkniętej dacie, należy wprowadzić datę otwartą i datę zamkniętą, aby wypełnić tę lukę.
- Po zakończeniu iteracji przez wejście, jeśli stan jest otwarty, wstaw końcową datę zamknięcia.
- Po zakończeniu iteracji przez wejście, jeśli stan jest zamknięty, a ostateczna data zamknięcia nie jest 9999-12-31. wstaw ostateczne otwarte i zamknięte daty.
0 dla odpowiedzi nr 2
Możesz najpierw wygenerować listę wszystkich otwartych dat, a następnie obliczyć daty zamknięcia, odejmując jeden dzień od każdej, ale pierwszą datę otwarcia:
Pseudo-kod C #:
var opendates = input.Select ( date =>
date.Type == closing ? date.Date + 1day : date.Date
).Sort ();
closingdates = opendates.Skip (1).Select (date => date - 1).Append ( new Date [] { 9999-12-31 } );
0 dla odpowiedzi № 3
Zatem rozwiązanie powinno być szybkie, ponieważ wydajnośćjest tutaj kluczowe. Powinien również obsługiwać przetwarzanie online, więc gdy system jest uruchomiony, możesz dodać nowe daty otwarcia / zamknięcia w dowolnym momencie i natychmiast otrzymać zaktualizowany harmonogram.
Ponieważ główną operacją w tym problemie jestsortowanie, sugerowałbym użycie kupy. Każdy węzeł w stercie przechowuje parę data / stan. Algorytm inicjuje pustą stertę i stale rozwija go jako wejścia do odczytu. Gdy pojawią się nowe dane, algorytm wstawia je do drzewa, które przyjmuje O (lgN). Gdy pojawi się żądanie pobrania harmonogramu, algorytm wykonuje poligon w kolejności, który przyjmuje O (N). Algorytm powinien również równoważyć się raz na jakiś czas, aby uzyskać lepszą wydajność.