Seeking an algorithm to efficiently layout calendar event banners

Question

I'm looking for an algorithm to efficiently place all-day/multi-day event banners, much like the month view in Outlook or Google Calendar. I have a number of events with a begin and end date, ordered by increasing begin (and then end) date (or any other order you please, I'm gathering events from a database table). I would like to minimize the average amount of vertical space used up, because after the event banners I will need to place other events just for that day (these always come after the banners for a given date). So, for example, if I had two events, one 1/10-1/11 and one 1/11-1/15, I would prefer to arrange them like so (each column is a single day):

 bbbbb
aa

and not like:

aa
 bbbbb

because when I add the events just for the day (x, y, and z), I can do this (I would prefer the first, do not want the second):

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

But it isn't as simple as placing the longer events first, because with 1/10-1/11, 1/13-1/14, and 1/11-1/13, I would want:

aa cc
 bbb

as opposed to:

 bbb
aa cc

because this would allow for events x and y:

aa cc    vs.     bbb
xbbby           aa cc
                x   y

And of course I would prefer to do this in one pass. For the data structure, I'm currently using a map from date to list, where for each day of an event I add the event to the corresponding list. So a three-day event appears in three lists,each one under one of the days in the map. This is a convenient structure for transforming the result into visual output, but I'm open to other data structures as well. I'm currently using a greedy algorithm, where I just add each event in order, but that can produce unwanted artifacts like:

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

This wastes a lot of space for most of the "e" event days.

Any ideas?

Answer 1

I think in a situation like this, you're much better off making sure your data is organized properly first and then rendering it. I know you want a single pass, but I think the results would be alot better.

For instance, organize the data into the lines you'll need to have for a given day and organize the events the best way possible, starting with the longest events (don't need to be displayed first, but they do need to be organized first) and moving down to the shortest events. This will allow you to render your output accordingly not wasting any space, and avoiding those "e" event days. Additionally, then:

 bbb
aa cc

or

aa cc
 bbb

won't matter because x and y can always go on either side of bbb or even between aa and cc

I hope you find this helpful.

Answer 2

Here is a high-level sketch of one possible solution (using day-of-week integers instead of full-blown dates). This 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);

}

must be implemented to use the algorithm expressed in the layout method below.

In addition, the concrete class must implement Comparable to create a natural order where longer events precede shorter events. (My sample implementation for the demo below used an order of descending length, then ascending start date, then ascending label.)

The layout method takes a collection of IEvent instances and returns a Map that assigns to each row in the presentation the set of events that can be shown in that row.

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

Each row is composed by selecting the longest remaining event and progressively selecting all additional events (in the order described above) that are compatible with previously-selected events for the current row. The effect is that all events "float" upward as far as possible without collision.

The following demo shows the two scenarios in your question, along with a randomly-created set of events.

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