title: Seeking an algorithm to efficiently layout calendar event banners
body: <p>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):</p>
  
  <pre><code> bbbbb
  aa
  </code></pre>
  
  <p>and not like:</p>
  
  <pre><code>aa
   bbbbb
  </code></pre>
  
  <p>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):</p>
  
  <pre><code> bbbbb    vs.    aa
  aa xyz            bbbbb
                      xyz
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>aa cc
   bbb
  </code></pre>
  
  <p>as opposed to:</p>
  
  <pre><code> bbb
  aa cc
  </code></pre>
  
  <p>because this would allow for events x and y:</p>
  
  <pre><code>aa cc    vs.     bbb
  xbbby           aa cc
                  x   y
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>aa ccc          
   bbbbb
      dd
       eeeeeeeeeeeeeeeee
  </code></pre>
  
  <p>This wastes a <em>lot</em> of space for most of the "e" event days.</p>
  
  <p>Any ideas?</p>