From: "Bryan R Harris" <[EMAIL PROTECTED]>
> I'm trying to come up with an algorithm that seems like it ought to be
> really easy, but it's turning out to be pretty tough...
>
> Basically I have three pairs of start/stop times, e.g.:
>
> 3, 5
> 4, 10
> 15, 20
>
> I want the total time covered by all these ranges. I can't just say
> (5-3 + 10-4 + 20-15) because the 3,5 and 4,10 ranges overlap. The
> desired answer for this case is 13, 3 to 10 and 15 to 20. I have the
> start times in two arrays, @starts and @stops.
>
> I have to do this probably a million+ times. Any ideas on how I could
> go about this?
Strange. Am I the only one who thinks about bitmaps as soon as
someone mentions unions?
Let's look at it like this. Each range specifies a set of hours, if we
implement the set as a bit map we can implement the union by
simple bitwise OR and then get the number of elements in the total
union by counting the 1s.
(I am assuming here that you only have full hours in the ranges and
that there are 24 hours a day (well, that there are at most 32 hours
a day actualy) and that range 1-3 is 2 hours long.
use strict;
my @ranges = ([2,5],[4,7],[12,14],[15,15]);
my $total = 0;
foreach my $int (@ranges) {
my $mask = 0xFFFFFFFF & (0xFFFFFFFF << ($int->[0]-
1));
$mask &= 0xFFFFFFFF >> (33-$int->[1]);
$total = $total | $mask;
print "$int->[0] .. $int->[1] = ", unpack("%32b*",
pack('N',$mask)), "\n";
}
print "Total: ", unpack("%32b*", pack('N',$total)), "\n";
Jenda
=========== [EMAIL PROTECTED] == http://Jenda.Krynicky.cz ==========
There is a reason for living. There must be. I've seen it somewhere.
It's just that in the mess on my table ... and in my brain
I can't find it.
--- me
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
