einen Algorithmus zum effizienten Layout Kalenderereignis Banner Suche nach dem

Question

Ich suche ein Algorithmus effizient alle-Tag / Mehrtag Banner Ereignis zu platzieren, ähnlich wie die Monatsansicht in Outlook oder Google Calendar. Ich habe eine Reihe von Veranstaltungen mit einem Anfangs- und Enddatum, geordnet durch die Erhöhung beginnen (und dann am Ende) Datum (oder einer anderen Reihenfolge Sie bitte, ich bin Ereignisse aus einer Datenbanktabelle zu sammeln). Ich mag die durchschnittliche Menge von vertikalem Raum minimieren verwendet, denn nach der Veranstaltung Bannern Ich werde andere Veranstaltungen stellen muß nur für diesen Tag (diese kamen immer nach den Bannern für ein bestimmtes Datum). So zum Beispiel, wenn ich zwei Ereignisse habe, ein 1 / 10-1 / 11 und eine 1 / 11-1 / 15, würde ich es vorziehen, sie wie so anzuordnen (jede Spalte ist ein einziger Tag):

 bbbbb
aa

und nicht mögen:

aa
 bbbbb

, denn wenn ich die Ereignisse nur für den Tag (x, y und z) hinzuzufügen, kann ich dies tun (ich die ersten bevorzugen würde, nicht die zweite will):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Aber es ist nicht so einfach, wie die längeren Ereignisse zuerst platzieren, weil mit 1 / 10-1 / 11, 1 / 13-1 / 14 und 1 / 11-1 / 13, ich möchte:

aa cc
 bbb

im Gegensatz zu:

 bbb
aa cc

, weil dies für Veranstaltungen x erlauben würde, und y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

Und natürlich würde ich es vorziehen, diese in einem Durchgang zu tun. Für die Datenstruktur, verwende ich derzeit eine Karte von Datum aufzulisten, wo für jeden Tag eines Ereignisses ich das Ereignis an die entsprechende Liste hinzuzufügen. So ein dreitägiges Ereignis wird in drei Listen, die jeweils unter einem des Tages in der Karte. Dies ist eine praktische Struktur für das Ergebnis in einem visuelle Ausgabe Transformation, aber ich bin offen für andere Datenstrukturen als auch. Ich bin derzeit mit einem Greedy-Algorithmus, wo ich jedes Ereignis fügen Sie einfach in Ordnung, aber das kann unerwünschte Artefakte erzeugen wie:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Dies verschwendet ein Los Platz für die meisten der "e" Veranstaltungstag.

Irgendwelche Ideen?

Answer 1

Hier ist eine High-Level-Skizze einer möglichen Lösung (Tag-of-Woche ganze Zahlen anstelle von ausgewachsenen Daten verwendet wird). Diese Schnittstelle:

public interface IEvent {

    public abstract int getFirst();  // first day of event
    public abstract int getLast();   // last day of event
    public abstract int getLength(); // total number of days
    public abstract char getLabel(); // one-char identifier

    // true if this and that have NO days in common
    public abstract boolean isCompatible(IEvent that);

    // true if this is is compatible with all events
    public abstract boolean isCompatibleWith(Collection<IEvent> events);

}

muß umgesetzt werden, um den Algorithmus in der layout Methode unten ausgedrückt zu verwenden.

Außerdem muss die konkrete Klasse Comparable implementieren eine natürliche Ordnung zu schaffen, wo mehr Ereignisse kürzer Ereignisse vorausgehen. (My Beispielimplementierung für die Demo unter verwendet, um eine Reihenfolge Länge absteigend, dann Startdatum aufsteigend, dann Label aufsteigend).

Die layout Methode nimmt eine Sammlung von IEvent Instanzen und gibt eine Map, die in der Darstellung der Menge von Ereignissen zu jeder Zeile zuordnet, die in dieser Zeile angezeigt werden kann.

public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) {
    Set<IEvent> remainingEvents = new TreeSet<IEvent>(events);
    Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>();
    int day = 0;
    while (0 < remainingEvents.size()) {
        Set<IEvent> dayEvents = new TreeSet<IEvent>();
        for(IEvent e : remainingEvents) {
            if (e.isCompatibleWith(dayEvents)) {
                dayEvents.add(e);
            }
        }
        remainingEvents.removeAll(dayEvents);
        result.put(day, dayEvents);
        ++day;
    }
    return result;
}

Jede Zeile wird zusammengesetzt, indem die längste verbleibende Ereignis auswählen und schrittweise alle zusätzlichen Ereignisse Auswählen (in der oben beschriebenen Reihenfolge), die mit vorher ausgewählten Ereignisse für die aktuelle Zeile kompatibel sind. Der Effekt ist, dass alle Ereignisse „float“ nach oben so weit wie möglich, ohne Kollision.

Die folgende Demo zeigt die beiden Szenarien in Frage, zusammen mit einem zufällig erstellten Satz von Ereignissen.

Event collection:
    x(1):4
    b(5):2..6
    y(1):5
    a(2):1..2
    z(1):6
Result of layout:
    0 -> {b(5):2..6}
    1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6}
Visual presentation:
      bbbbb
     aa xyz

Event collection:
    x(1):1
    b(3):2..4
    a(2):1..2
    c(2):4..5
    y(1):5
Result of layout:
    0 -> {b(3):2..4, x(1):1, y(1):5}
    1 -> {a(2):1..2, c(2):4..5}
Visual presentation:
     xbbby 
     aa cc 

Event collection:
    f(2):1..2
    h(2):1..2
    d(4):1..4
    e(4):2..5
    c(1):6
    a(2):5..6
    g(4):2..5
    b(2):0..1
Result of layout:
    0 -> {d(4):1..4, a(2):5..6}
    1 -> {e(4):2..5, b(2):0..1, c(1):6}
    2 -> {g(4):2..5}
    3 -> {f(2):1..2}
    4 -> {h(2):1..2}
Visual presentation:
     ddddaa
    bbeeeec
      gggg 
     ff    
     hh    

Answer 2

Ich denke, in einer Situation wie dieser, sind Sie viel besser sicherstellen, dass Ihre Daten richtig ersten organisiert ist und wodurch es dann. Ich weiß, dass Sie einen einzigen Pass wollen, aber ich denke, die Ergebnisse besser alot würde.

Zum Beispiel, um die Daten in die Leitungen organisieren Sie für einen bestimmten Tag haben müssen, und die Ereignisse, die beste Art und Weise möglich zu organisieren, mit den längsten Veranstaltungen beginnen (muß nicht erst angezeigt werden, aber sie brauchen organisiert zuerst) und nach unten bewegen, um die kürzesten Ereignissen werden. Dies ermöglicht Ihnen, Ihre Ausgabe entsprechend nicht verschwenden, jeden Raum und die Vermeidung von diesen „e“ Ereignis Tag zu machen. Zusätzlich dann:

 bbb
aa cc

oder

aa cc
 bbb

wird keine Rolle, weil x und y immer auf beiden Seiten des bbb gehen können oder sogar zwischen aa und cc

Ich hoffe, dass Sie diese hilfreich finden.