Algorithm::TimelinePacking: arranging overlapping intervals into lanes
A small Perl module that packs overlapping time intervals into the minimum number of non-overlapping rows. Originally for visualising Hadoop job timelines; works for any Gantt-style layout.
Years ago I had a problem at work: visualise a few hundred Hadoop MapReduce jobs as a timeline, with each job a coloured bar from its start to its end. The jobs overlapped heavily, so the question was which row each bar should go on — using as few rows as possible (the visualisation had to fit on a screen) without putting two overlapping bars on the same row. Algorithm::TimelinePacking is the small Perl module that came out of that.
Greedy first-fit, provably optimal
This is the interval graph colouring problem in disguise, and the greedy first-fit solution is the textbook one: take each interval in order, drop it on the first row where it fits, create a new row when needed. The minimum number of rows is provably equal to the maximum overlap depth, and the implementation is twenty lines.
A surprising number of “scheduling” and “packing” problems turn out to be textbook problems wearing different vocabulary; checking before designing is usually worth a few minutes.
Generic API
The original use case was Hadoop, but Hadoop has nothing to do with the algorithm. The module takes [start, end, ...metadata] tuples, where the metadata is opaque to the packer and free for the caller to use. The example folder includes a conference schedule packer; the same module would work for meeting rooms, TV programming, project Gantts, or resource booking.
An algorithm module that knows about its caller’s domain stops being reusable; this one stays restricted to intervals.
Was it worth it?
It’s old code. The version is still 0.01. The algorithm doesn’t age, and the module still does what it said it would.
dmorel69/Algorithm-TimelinePacking— Perl, CPAN-style