Algorithm for stacking events/items

Question

I'm looking to build a pseudo Gantt chart, except one where events can be on the same line as long as they don't overlap, something like this:

               M T W R F S U M T W R F S U M T W R F S U
Category 1:   |Event 1|     |Event 2| |------Event 3--|
                |---------Event 4-----------| |-Event 5-|

I'm looking for an algorithm to efficiently pack these events. I know I can use the length of event and the start date to determine overlapping, but I'd like to have some kind of starting point.

For the curious, I'm looking at getting around limitations of the Gantt calendar view in SharePoint 2007. Our users like that view, but don't want one task per line.

Answer 1

My first attempt would be to sort the tasks by start time/date. Then I'd place them one at a time on the first line on which their start time wasn't already occupied. I'm not (at all) sure that gives optimal results (i.e., always uses the smallest number of lines possible), but it should at least be halfway reasonable.

The more I think about it, however, the more I think it might actually be optimal. Optimization problems are usually difficult because the number of combinations rises extremely quickly compared to the number of items. In this case, however, you don't really get such a combinatorial explosion because you can't rearrange items -- at least I'm assuming their start times are all pre-set, so they can't be rearranged.

Edit: just to be clear: here I'm assuming that the question deals only with displaying a schedule of events for which the start times and durations are already known, so optimization just means displaying the data as "compactly" as possible. I'm not talking about attempting to create the schedule itself (i.e., attempting to figure out what events to schedule when). Depending on the constraints involved, that's normally a much more difficult problem. It's fairly easy as long as your only constraints are inter-task dependencies, but when you add things like maximum manpower usage and constrained resources (e.g., task X can only be carried out by person A, B, or C, task Y by B, C or D, etc.), the situation becomes much more difficult very quickly.