my @box;
for (...) {
my ($NetName, $MinX, $MinY, $MaxX, $MaxY) = ...;
push @box, [$NetName,
$MinX, $MinY, $MaxX, $MaxY,
($MaxX - $MinX) * ($MaxY - $MinY)];
}
####
@box = sort { $a->[5] <=> $b->[5] } @box;
##
##
use Sort::Key qw(nkeysort_inplace);
nkeysort_inplace { $_->[5] } @box;
##
##
# untested!
my ($area, @best) = n_largest_boxes(\@box, $n);
sub overlap {
my ($box1, $box2) = @_;
return !( $box1->[3] < $box2->[1] or
$box1->[1] > $box2->[3] or
$box1->[4] < $box2->[2] or
$box1->[2] > $box2->[4] )
}
sub n_largest_boxes {
my ($boxes, $n, $start, @acu) = @_;
my $max = 0; # area for the biggest set of boxes found
my @max; # rectangles on the biggest set
for ($i = $start || 0;
$i + $n <= @$boxes and $boxes->[$i][5] * $n > $max;
$i++) {
my $box = $boxes->[$i];
next if grep overlap($_, $box), @acu;
if ($n > 1) {
my $max1, @max1 = n_largest_boxes($boxes, $i+1, $n-1,
@acu, $box);
if ($max1 and $max1 + $box->[5] > $max) {
$max = $max1 + $box->[5];
@max = ($box, @max1);
}
}
else {
return ($box->[5], $box);
}
}
return ($max, @max);
}