#!/usr/bin/perl

use Data::Dump qw/pp/;
use warnings;
use strict;

my $interval = 4;
my %hash = (
    3 => [ 1 .. 2 ],
    4 => [ 2 .. 2 ],
    6 => [ 4 .. 5 ],
    7 => [ 2 .. 6 ],
    8 => [ 1 .. 3 ],
   11 => [ 5 .. 10 ],
);

sub fill {
    my ($return, $stack) = @_;
    while ($return->[-1] - $return->[0] <= $interval) {
        my $next = shift @$stack;
        push @$return, $next;
        last unless defined $next;
    }
    unshift @$stack, pop @$return;
    pop @$stack if 1 == @$stack and not defined $stack->[0];
} # fill

sub process {
    my ($i, $j) = @_;
    my @arrays = @hash{($i,$j)};
    if (@{ $arrays[0] } > @{ $arrays[1] }) {
        push @arrays, shift @arrays;
    }
    return map [ ($arrays[0][$_]//0) + $arrays[1][$_] ],
               0 .. @{ $arrays[1] } - 1;
} # process


my @indexes = sort {$a <=> $b} keys %hash;
my @pool = shift @indexes;
fill(\@pool, \@indexes);

my %cache;
while (@pool) {
    for my $i (@pool) {
        for my $j (grep $_ > $i, @pool) {
            $cache{"$i,$j"} //= [process($i, $j)];
        }
    }
    pp ['Pool: ', @pool, 'Cache: ', %cache, 'Idx: ', @indexes];

    my $delete = shift @pool;
    # skip this if you have enough memory:
    delete $cache{"$delete,$_"} for @pool;

    last unless @indexes;
    fill(\@pool, \@indexes);
}
[download]