#! perl -slw
use strict;
use Data::Dumper;
use List::Util qw[ reduce first ];

our $N ||= 100;
our $MIN ||= 10;

my @data = sort{
    $a->[ 0 ] <=> $b->[ 0 ]
} map{
    [ rand 1000, 1+ int rand 9 ]
} 1 .. $N;
#print Dumper \@data;

my $min = reduce{ $a->[0] < $b->[ 0 ] ? $a : $b } @data;
my $max = reduce{ $a->[0] > $b->[ 0 ] ? $a : $b } @data;
my $gap = ( $max->[ 0 ] - $min->[ 0 ] ) / $MIN ;
#print "$min->[0]:$max->[0]:$gap";

my @buckets;
push @{ $buckets[
    ( $data[ $_ ][ 0 ] - $min->[ 0 ] -1 ) / $gap
] }, $data[ $_ ] for 0 .. $#data;
#print Dumper \@buckets;

my @selected;
for my $bucket ( 0 .. $#buckets ) {
    my $mid = (( $bucket+1 ) * $gap ) - ( $gap / 2 ) + $min->[ 0 ];
    $selected[ $bucket ] = (
        map{
            $_->[ 1 ]
        } sort {
            $a->[ 0 ] <=> $b->[ 0 ]
        } map {
           [ abs( $_->[ 0 ] - $mid ) / ( $_->[ 1 ]||1 ), $_ ]
        } @{ $buckets[ $bucket ] }
    )[ 0 ];
}

my $next = 0;
my $group = $min->[ 0 ];
printf "\nGroup: %f - %f; median: %f\n",
    $group, $group + $gap, $group + ( $gap / 2 );
$group += $gap;

for my $idx ( 0 .. $#data ) {
    if( $data[ $idx ][ 0 ] > $group ) {
        printf "\nGroup: %f - %f; median: %f\n",
            $group, $group + $gap, $group + ( $gap / 2 );
        $group += $gap;
    }
    my $selected = ' ';
    if( $next < @selected and $data[ $idx ][ 0 ] == $selected[ $next ][ 0 ] ) {
        $selected = $next;
        ++$next;
    }
    printf "%1s\t[ @{ $data[ $idx ] } ]\n", $selected;
}