Recherche d'un algorithme pour la mise en page efficace des bannières d'événements de calendrier

Question

Je recherche un algorithme pour placer efficacement des bannières d’événements toute la journée ou sur plusieurs jours, un peu comme la vue mensuelle dans Outlook ou Google Agenda. J'ai un certain nombre d'événements avec une date de début et de fin, classés en augmentant la date de début (puis de fin) (ou toute autre commande qui vous convient, je rassemble des événements à partir d'une table de base de données). J'aimerais minimiser la quantité moyenne d'espace vertical utilisé, car après les bannières, il me faudra placer d'autres événements juste pour ce jour-là (ceux-ci suivent toujours les bannières à une date donnée). Ainsi, par exemple, si j’avais deux événements, un 1 / 10-1 / 11 et un 1 / 11-1 / 15, je préférerais les organiser comme suit (chaque colonne est un seul jour):

 bbbbb
aa

et pas comme:

aa
 bbbbb

parce que quand j'ajoute les événements du jour (x, y et z), je peux le faire (je préférerais le premier, je ne veux pas le second):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Mais ce n’est pas aussi simple que de placer les événements les plus longs en premier, car avec 1 / 10-1 / 11, 1 / 13-1 / 14 et 1 / 11-1 / 13, je voudrais:

aa cc
 bbb

par opposition à:

 bbb
aa cc

car cela autoriserait les événements x et y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

Et bien sûr, je préférerais faire cela en un seul passage. Pour la structure de données, j'utilise actuellement une carte de date à liste, où, pour chaque jour d'un événement, j'ajoute l'événement à la liste correspondante. Ainsi, un événement de trois jours apparaît dans trois listes, chacune sous l'un des jours de la carte. Il s'agit d'une structure pratique pour transformer le résultat en sortie visuelle, mais je suis également ouvert à d'autres structures de données. J'utilise actuellement un algorithme glouton. J'ajoute simplement chaque événement dans l'ordre, mais cela peut produire des artefacts indésirables, tels que:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Ceci gaspille beaucoup d'espace pour la plupart des "e"; jours d’événement.

Des idées?

Answer 1

Voici un aperçu général d'une solution possible (utilisant des entiers du jour de la semaine au lieu de dates complètes). Cette interface:

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);

}

doit être implémenté pour utiliser l'algorithme exprimé dans la méthode layout ci-dessous.

De plus, la classe concrète doit implémenter Comparable pour créer un ordre naturel dans lequel des événements plus longs précèdent des événements plus courts. (Mon exemple d'implémentation pour la démo ci-dessous utilisait un ordre de longueur décroissant, puis une date de début croissante, puis un libellé croissant.)

La méthode layout prend une collection d'instances IEvent et retourne une Map qui attribue à chaque ligne de la présentation l'ensemble d'événements peut être affiché dans cette rangée.

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;
}

Chaque ligne est composée en sélectionnant l'événement restant le plus long, puis en sélectionnant progressivement tous les événements supplémentaires (dans l'ordre décrit ci-dessus) compatibles avec les événements précédemment sélectionnés pour la ligne en cours. L’effet est que tous les événements & flo; float " dans la mesure du possible sans collision.

La démo suivante présente les deux scénarios de votre question, ainsi qu'un ensemble d'événements créés de manière aléatoire.

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

Je pense que dans une situation comme celle-ci, vous feriez bien mieux de vous assurer que vos données sont bien organisées, puis de les restituer. Je sais que vous voulez un seul laissez-passer, mais je pense que les résultats seraient bien meilleurs.

Par exemple, organisez les données dans les lignes nécessaires pour un jour donné et organisez les événements de la meilleure façon possible, en commençant par les événements les plus longs (il n'est pas nécessaire de les afficher au préalable, mais ils doivent être organisé en premier) et descendre aux événements les plus courts. Cela vous permettra de rendre votre sortie en conséquence, sans gaspiller d’espace, et en évitant celles-ci "e". jours d'événement. De plus, alors:

 bbb
aa cc

ou

aa cc
 bbb

n'aura pas d'importance, car x et y peuvent toujours figurer de part et d'autre de bbb ou même entre aa et cc

J'espère que vous trouverez cela utile.