Ereignisse Zeitplan Verpackung

Question

Ich bin auf Zeitplan für Schulzwecke arbeiten. Ich erhalte eine zeitlich geordnete Liste von Ereignissen und mein Ziel ist es, sie auf der Zeitachse zu zeichnen. Das Problem ist, dass ein Ereignis ein anderes überlagert (wie in der Abbildung unten gezeigt). Ich möchte diese Ereignisse auf kleinstem Raum "packen". This is single day with overlapping events.

erstes Bild zeigt, was ich bisher tun verwaltet. Wie auf dem Bild zu sehen, überschneiden sich die Rechtecke nicht und füllen den freien Platz gut aus. Aber ich habe es nicht geschafft, einen vernünftigen Algorithmus für die Bestellung zu finden. Second picture shows how events should be ordered.

Dies sind zwei Bedingungen, die dieses Problem unterscheidet sich von klassischen Verpackungs Problem machen:

1. Ereignisse gegeben hat, x-Koordinaten (von Anfang und Ende definiert).
2. Events hat eine feste Breite, Höhe ist beliebig.

Answer 1

Dieses Problem erinnert mich ein wenig Fragmentierungsproblem Dateisystem. Einfache Lösungen wären die Implementierung eines bekannten Algorithmus, z. First-Fit oder Best-Fit.

Aber ich denke, Ihnen die beste Lösung wollen. Deshalb würde ich vorschlagen, eine backtracking algorithm zu implementieren. Seien Sie sich bewusst, dass ich lange Laufzeiten verursachen kann, aber ich denke, dass dies in Ihrem Kontext keine Rolle spielt.