#! 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;
}

##</code><code>##

C:\test>550135-2 -N=50

Group: 48.675537 - 143.658447; median: 96.166992
        [ 48.675537109375 6 ]
*       [ 67.138671875 8 ]
        [ 77.545166015625 1 ]
        [ 81.23779296875 1 ]
        [ 120.941162109375 1 ]
        [ 135.650634765625 1 ]
        [ 138.427734375 1 ]

Group: 143.658447 - 238.641357; median: 191.149902
        [ 149.139404296875 1 ]
        [ 161.651611328125 5 ]
*       [ 205.841064453125 6 ]

Group: 238.641357 - 333.624268; median: 286.132813
        [ 247.1923828125 9 ]
        [ 290.6494140625 2 ]
*       [ 294.525146484375 7 ]
        [ 309.14306640625 7 ]
        [ 331.085205078125 1 ]

Group: 333.624268 - 428.607178; median: 381.115723
        [ 349.822998046875 6 ]
        [ 351.4404296875 5 ]
*       [ 394.287109375 7 ]
        [ 396.636962890625 6 ]
        [ 416.290283203125 8 ]

Group: 428.607178 - 523.590088; median: 476.098633
*       [ 492.340087890625 1 ]

Group: 523.590088 - 618.572998; median: 571.081543
        [ 528.961181640625 4 ]
        [ 540.863037109375 9 ]
        [ 561.82861328125 2 ]
        [ 565.155029296875 2 ]
        [ 575.531005859375 2 ]
*       [ 579.437255859375 5 ]
        [ 592.864990234375 6 ]

Group: 618.572998 - 713.555908; median: 666.064453
        [ 627.166748046875 7 ]
        [ 633.23974609375 6 ]
        [ 643.829345703125 6 ]
*       [ 647.88818359375 9 ]

Group: 713.555908 - 808.538818; median: 761.047363
        [ 736.81640625 6 ]
*       [ 751.8310546875 6 ]
        [ 778.01513671875 9 ]

Group: 808.538818 - 903.521729; median: 856.030273
        [ 826.7822265625 6 ]
        [ 827.0263671875 3 ]
        [ 846.649169921875 1 ]
*       [ 869.32373046875 5 ]
        [ 880.55419921875 9 ]
        [ 883.6669921875 7 ]
        [ 891.2353515625 8 ]
        [ 901.55029296875 9 ]

Group: 903.521729 - 998.504639; median: 951.013184
        [ 906.73828125 4 ]
        [ 909.881591796875 1 ]
*       [ 939.75830078125 7 ]
        [ 992.49267578125 1 ]
        [ 993.499755859375 1 ]
        [ 997.4365234375 3 ]
        [ 998.504638671875 1 ]