Buscando um algoritmo para eficientemente layout de banners de eventos de calendário

Question

Eu estou procurando um algoritmo para colocar de forma eficiente todos os dias banners de eventos / multi-dia, bem como a vista mensal no Outlook ou Google Calendar. Eu tenho um número de eventos com um início e fim data, ordenou aumentando começar (e acabar) data (ou qualquer outra ordem, por favor, eu estou reunindo eventos de uma tabela de banco de dados). Gostaria de minimizar a quantidade média de espaço vertical usado para cima, porque depois os banners do evento vou precisar para colocar outros eventos apenas para esse dia (estes vêm sempre depois dos banners para uma determinada data). Assim, por exemplo, se eu tivesse dois eventos, um 1 / 10-1 / 11 e um 1 / 11-1 / 15, eu preferiria organizá-los assim (cada coluna há um único dia):

 bbbbb
aa

e não como:

aa
 bbbbb

porque quando eu adicionar os eventos apenas para o dia (x, y, e z), eu posso fazer isso (eu prefiro o primeiro, não quer que o segundo):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

Mas não é tão simples como colocar os eventos mais longos primeiro lugar, porque com 1 / 10-1 / 11, 1 / 13-1 / 14 e 1 / 11-1 / 13, eu gostaria:

aa cc
 bbb

em oposição a:

 bbb
aa cc

porque isso permitiria eventos x e y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

E é claro que eu preferiria fazer isso em uma passagem. Para a estrutura de dados, Atualmente estou usando um mapa a partir da data de lista, onde para cada dia de um evento que eu adicionar o evento à lista correspondente. Assim, um evento de três dias aparece em três listas, cada um sob um dos dias do mapa. Esta é uma estrutura conveniente para transformar o resultado na saída visual, mas estou aberto a outras estruturas de dados também. Atualmente estou usando um algoritmo guloso, onde basta adicionar cada evento em ordem, mas que pode produzir artefatos indesejados como:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

Este desperdiça muito de espaço para a maioria dos "e" dias de evento.

Todas as idéias?

Answer 1

Aqui está um esboço de alto nível de uma solução possível (usando números inteiros dia-de-semana em vez de datas full-blown). Esta 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);

}

devem ser implementadas para usar o algoritmo expressa no método layout abaixo.

Além disso, a classe concreta deve implementar Comparable para criar uma ordem natural onde os eventos mais longos preceder eventos mais curtos. (My implementação de exemplo para a demonstração abaixo usou uma ordem decrescente de comprimento, então ascendente data de início, então ascendente rótulo.)

O método layout leva uma coleção de instâncias IEvent e retorna um Map que atribui a cada linha na apresentação do conjunto de eventos que pode ser mostrado nessa linha.

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 linha é composta por selecionando o mais longo evento restantes e selecionando progressivamente todos os eventos adicionais (na ordem descrita acima) que são compatíveis com eventos previamente selecionados para a linha atual. O efeito é que todos os eventos "flutuar" para cima, tanto quanto possível sem colisão.

A seguir mostra demonstração os dois cenários em sua pergunta, junto com um conjunto aleatório-criado de eventos.

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

Eu acho que em uma situação como esta, você está muito melhor ter certeza que seus dados são organizados corretamente em primeiro lugar e, em seguida, tornando-o. Eu sei que você quer uma única passagem, mas acho que os resultados seriam muito melhor.

Por exemplo, organizar os dados nas linhas que você precisa ter para um determinado dia e organizar os eventos da melhor maneira possível, começando com os eventos mais longos (não precisa ser exibido pela primeira vez, mas eles precisam a ser organizada pela primeira vez) e movendo-se para baixo para os eventos mais curtos. Isso permitirá que você para tornar a sua saída de acordo não desperdiçar qualquer espaço, e evitar aquelas "e" dias de evento. Além disso, a seguir:

 bbb
aa cc

ou

aa cc
 bbb

não importará porque x e y pode sempre ir em cada lado da bbb ou mesmo entre aa e cc

Eu espero que você encontrar este útil.