Buscando un algoritmo para diseñar eficientemente banners de eventos de calendario

Question

Estoy buscando un algoritmo para colocar de manera eficiente pancartas de eventos de todo el día / de varios días, como la vista mensual en Outlook o Google Calendar. Tengo varios eventos con una fecha de inicio y finalización, ordenados al aumentar la fecha de inicio (y luego de finalización) (o cualquier otra orden que desee, estoy recopilando eventos de una tabla de base de datos). Me gustaría minimizar la cantidad promedio de espacio vertical utilizado, ya que después del evento tendré que colocar otros eventos solo para ese día (estos siempre vienen después de los banners para una fecha determinada). Entonces, por ejemplo, si tuviera dos eventos, uno 1 / 10-1 / 11 y uno 1 / 11-1 / 15, preferiría organizarlos así (cada columna es un solo día):

 bbbbb
aa

y no como:

aa
 bbbbb

porque cuando agrego los eventos solo por el día (x, y, yz), puedo hacer esto (preferiría el primero, no quiero el segundo):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Pero no es tan simple como colocar primero los eventos más largos, porque con 1 / 10-1 / 11, 1 / 13-1 / 14 y 1 / 11-1 / 13, querría:

aa cc
 bbb

a diferencia de:

 bbb
aa cc

porque esto permitiría eventos xey:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

Y, por supuesto, preferiría hacer esto en una sola pasada. Para la estructura de datos, actualmente estoy usando un mapa desde la fecha a la lista, donde para cada día de un evento agrego el evento a la lista correspondiente. Entonces, un evento de tres días aparece en tres listas, cada una debajo de uno de los días en el mapa. Esta es una estructura conveniente para transformar el resultado en una salida visual, pero también estoy abierto a otras estructuras de datos. Actualmente estoy usando un algoritmo codicioso, donde solo agrego cada evento en orden, pero eso puede producir artefactos no deseados como:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Esto desperdicia un lote de espacio para la mayoría de las " e " días de evento.

¿Alguna idea?

Answer 1

Aquí hay un bosquejo de alto nivel de una posible solución (utilizando números enteros del día de la semana en lugar de fechas completas). Esta interfaz:

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

}

debe implementarse para utilizar el algoritmo expresado en el método layout a continuación.

Además, la clase concreta debe implementar Comparable para crear un orden natural donde los eventos más largos preceden a los eventos más cortos. (La implementación de mi muestra para la siguiente demostración utilizó un orden de longitud descendente, luego fecha de inicio ascendente y luego etiqueta ascendente).

El método

layout toma una colección de instancias de IEvent y devuelve un Mapa que asigna a cada fila de la presentación el conjunto de eventos que se puede mostrar en esa fila.

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

Cada fila se compone seleccionando el evento restante más largo y seleccionando progresivamente todos los eventos adicionales (en el orden descrito anteriormente) que son compatibles con los eventos seleccionados previamente para la fila actual. El efecto es que todos los eventos " float " hacia arriba en la medida de lo posible sin colisión.

La siguiente demostración muestra los dos escenarios de su pregunta, junto con un conjunto de eventos creados al azar.

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

Creo que en una situación como esta, es mucho mejor asegurarse de que sus datos estén organizados correctamente primero y luego procesarlos. Sé que quieres un solo pase, pero creo que los resultados serían mucho mejores.

Por ejemplo, organice los datos en las líneas que necesitará para un día determinado y organice los eventos de la mejor manera posible, comenzando con los eventos más largos (no es necesario que se muestren primero, pero sí es necesario organizarse primero) y pasar a los eventos más cortos. Esto le permitirá representar su salida en consecuencia, sin desperdiciar espacio, y evitando esos " e " Días de evento. Además, entonces:

 bbb
aa cc

o

aa cc
 bbb

no importará porque x y y siempre pueden ir en cualquier lado de bbb o incluso entre aa y cc

Espero que te resulte útil.