A hash is not the right structure for this problem. You should use an array:
my @box;
for (...) {
my ($NetName, $MinX, $MinY, $MaxX, $MaxY) = ...;
push @box, [$NetName,
$MinX, $MinY, $MaxX, $MaxY,
($MaxX - $MinX) * ($MaxY - $MinY)];
}
and you can sort it as:
@box = sort { $a->[5] <=> $b->[5] } @box;
or if that sort results too slow:
use Sort::Key qw(nkeysort_inplace);
nkeysort_inplace { $_->[5] } @box;
Then, you have to look for the N largest areas. It can be done recursively: get the biggest rectangle and look for the N-1 largest, non-overlapping areas.
BTW, "the N largest boxes" is not very precise. Which is larger, a set of rectangles with areas (9, 1) or another with (7, 6)?
I suppose you want to maximize the total area:
# 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);
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.