Gegeben eine Reihe von Eingabedaten mit einem einzigenentweder Open oder Closed, so dass mindestens ein Eingabedatum (offener Zustand) vorhanden ist, was dazu führt, dass ein einziges Datum (Closed, Max Date) zur Vervollständigung der Ausgabefolge hinzugefügt wird. Welchen Algorithmus würden Sie zur Generierung der Ausgabe verwenden? gehorcht das folgende?
1. Es gibt keine aufeinanderfolgenden offenen Daten und keine aufeinanderfolgenden geschlossenen Daten.
2. Für jedes Open-Datum gibt es genau ein Closed-Datum.
3. Das erste Datum sollte offen sein und das letzte Datum sollte geschlossen sein.
4. Abgesehen vom ersten Eröffnungsdatum und dem letzten Geschlossenen Datum sollte jedes Eröffnungsdatum unmittelbar dem vorherigen Geschlossenen Datum folgen, oder anders ausgedrückt, jedes Geschlossene Datum sollte der Tag vor dem nächsten Eröffnungsdatum sein.
5. Das Enddatum ist Closed und Max date (9999-12-31, in diesem Beispiel)
Dies ist keine Hausaufgabe, die ich umgesetzt habedas ist in C # und es ist der Produktionscode, der millionenfach ausgeführt wird. Leistung ist wichtig, ja, aber sehr sekundär zur Lesbarkeit. Der Algorithmus, den ich benutzt habe, funktioniert einwandfrei, sieht aber schrecklich aus. Jede Sprache ist willkommen. Ich werde übersetzen wie nötig. Danke.
Beispiel 1
input:
[2000-01-01,open]
output:
[2000-01-01,open]
[9999-12-31,closed]
Beispiel 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]
Beispiel 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]
Beispiel 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]
Darf ich fragen, welche Klasse von Sprache diese Art von Problem am besten löst?
Antworten:
5 für die Antwort № 1- Sortieren Sie die Eingabe nach Datum.
- Iterieren durch die Eingabe und verfolgen den aktuellen Status.
- Wenn der Status offen ist und ein offenes Datum angetroffen wird, fügen Sie ein geschlossenes Datum ein.
- Wenn der Status geschlossen ist und ein geschlossenes Datum auftritt, fügen Sie ein Eröffnungsdatum ein.
- Wenn der Status geschlossen ist und ein offenes Datum gefunden wurde, das nicht der Tag nach dem vorherigen geschlossenen Datum ist, fügen Sie ein offenes Datum und ein geschlossenes Datum ein, um diese Lücke zu füllen.
- Fügen Sie nach Abschluss der Iteration durch die Eingabe das endgültige Abschlussdatum ein, wenn der Status offen ist.
- Wenn das Iterieren durch Eingabe ausgeführt wird, wenn der Status geschlossen ist und das abgeschlossene Enddatum nicht 9999-12-31 ist. Fügen Sie die endgültigen offenen und geschlossenen Daten ein.
0 für die Antwort № 2
Sie können zunächst eine Liste aller offenen Daten generieren und dann die Abschlussdaten berechnen, indem Sie einen Tag von jedem bis auf das erste Eröffnungsdatum subtrahieren:
C # -Pseudocode:
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 für die Antwort № 3
Also sollte die Lösung schnell sein, da die Leistung istist hier entscheidend. Außerdem sollte es die Online-Verarbeitung unterstützen. Wenn das System läuft, können Sie jederzeit neue Öffnungs- und Schließungsdaten hinzufügen und sofort einen aktualisierten Zeitplan erhalten.
Da ist die Hauptoperation in diesem ProblemSortieren würde ich vorschlagen, einen Haufen zu verwenden. Jeder Knoten im Heap speichert ein Datums- / Zustandspaar. Der Algorithmus startet mit einem leeren Heap und entwickelt ihn kontinuierlich als Leseeingaben weiter. Wenn neue Daten kommen, fügt der Algorithmus sie in den Baum ein, der O (lgN) benötigt. Wenn eine Anfrage zum Ziehen eines Zeitplans vorliegt, führt der Algorithmus eine Intra-Order-Traverse durch, die O (N) benötigt. Der Algorithmus sollte sich auch einmal für eine bessere Leistung ausgleichen.