view release on metacpan or  search on metacpan

README.md  view on Meta::CPAN

The algorithm uses a greedy first-fit approach, placing each interval on the
first available line where it fits without overlap.

# EXAMPLES

## Conference Schedule

Arrange talks into rooms so no two talks overlap in the same room:

    use Algorithm::TimelinePacking;

    my $packer = Algorithm::TimelinePacking->new(space => 15);  # 15 min between talks

    # Talks: [start_minutes, end_minutes, title, speaker, track]
    my @talks = (
        [540,  600, 'Opening Keynote',       'Margot Tenenbaum', 'keynote'],
        [600,  645, 'GopherScript for Beginners', 'Kevin McCallister', 'beginner'],
        [600,  645, 'Advanced Burrow Patterns',   'Ferris Mueller', 'advanced'],
        [600,  690, 'Workshop: Testing',     'Beatrix Bourbon', 'workshop'],
        [660,  705, 'Database Wrangling',    'Chester Copperpot', 'beginner'],
        [660,  705, 'Unsafe Memory Access',  'Wanda Maximoff', 'advanced'],
        [720,  780, 'Lunch',                 '',        'break'],
        [780,  825, 'Async/Await Deep Dive', 'Inigo Montoya', 'advanced'],
        [780,  870, 'Workshop: Web Apps',    'Rufus Firefly', 'workshop'],
        [840,  900, 'Closing Panel',         'Various', 'keynote'],
    );

    my ($rooms, $end) = $packer->arrange_slices(\@talks);

    for my $i (0 .. $#$rooms) {
        print "Room ", $i + 1, ":\n";
        for my $talk (@{$rooms->[$i]}) {
            printf "  %02d:%02d - %s (%s)\n",
                int($talk->[0] / 60), $talk->[0] % 60,
                $talk->[2], $talk->[3];
        }
    }

    # Output shows minimum rooms needed, with no scheduling conflicts

## Hadoop Job Timeline

The original use case - visualize MapReduce job execution:

    my @jobs = (
        [$start_epoch, $end_epoch, $job_id, $user, $map_tasks, $reduce_tasks],
        ...
    );

    my ($lines, $latest) = $packer->arrange_slices(\@jobs);
    # Feed $lines to D3.js or other visualization library

# ATTRIBUTES

## space

    my $packer = Algorithm::TimelinePacking->new(space => 10);

Minimum space (in the same units as your timestamps) required between
consecutive intervals on the same line. Default: 0.

## width

    my $packer = Algorithm::TimelinePacking->new(width => 800);

If set, all intervals will be scaled to fit within this width. The scaling
preserves relative positions and durations. Default: undef (no scaling).

# METHODS

## arrange\_slices

    my ($lines, $latest) = $packer->arrange_slices(\@slices);

Takes an arrayref of slices and returns:

- `$lines` - arrayref of lines, each containing non-overlapping slices
- `$latest` - the normalized maximum end timestamp

Each input slice must be an arrayref where the first two elements are
start and end timestamps. Additional elements (metadata) are preserved.

    [start, end, ...optional_metadata]

The slices are modified in place (normalized to start at 0, optionally scaled).

# ALGORITHM

The packing uses a greedy first-fit approach:

1. Sort intervals by start time (secondary sort by end time)
2. Normalize all timestamps to start at 0
3. Optionally scale to fit within specified width
4. For each interval, place it on the first line where it fits
5. If no line has room, create a new line
6. Shuffle the final line order for visual balance

Time complexity: O(n² log n) where n is the number of intervals.

# AUTHOR

David Morel <david.morel@amakuru.net>

# LICENSE

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.