Maybe I'm recreating the wheel here, but wouldn't the following work for you?
#!/usr/bin/perl
my @data = (
[ 2, 8 ],
[ 1, 3 ],
[ 4, 6 ],
[ 7, 10 ],
[ 8, 20 ],
);
foreach my $pair (@data)
{
@{$pair}[1,0] = @{$pair}[1,0]
if $pair->[0] > $pair->[1];
$pair->[2] = $pair->[1] - $pair->[0];
}
@data = sort { $a->[2] cmp $b->[2] || $a->[0] cmp $b->[0] || $a->[1] c
+mp $b->[1] } @data;
my @good;
PAIR:
foreach my $pair (@data)
{
my @check;
foreach my $i (0 .. $#good)
{
my $good = $good[$i];
if (
($good->[0] <= $pair->[0] && $pair->[0] < $goo
+d->[1])
||
($good->[0] < $pair->[1] && $pair->[1] <= $goo
+d->[1])
||
($pair->[0] <= $good->[0] && $good->[0] < $pai
+r->[1])
||
($pair->[0] < $good->[1] && $good->[1] <= $pai
+r->[1])
) {
push @check, [
$good,
$i,
];
}
}
unless (@check)
{
push @good, $pair;
next PAIR;
}
my $max = 0;
$max += $_->[2] for map { $_->[0] } @check;
next PAIR if $max > $pair->[2];
splice @good, $_, 1 for sort { $b <=> $a } map { $_->[1] } @ch
+eck;
push @good, $pair;
}
@good = sort { $a->[0] cmp $b->[0] || $a->[1] cmp $b->[1] } @good;
print "$_->[0] ... $_->[1] ($_->[2])\n" for @good;
my $cover = 0;
$cover += $_->[2] for @good;
print "Total coverage is $cover\n";
------
We are the carpenters and bricklayers of the Information Age.
The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6
Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.
-
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.