> 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?
Oh... a million? Better be a fast ALGORITHM:
use constant START => 0;
use constant END => 1;
my @timeslices = (
[4, 9],
[3, 6],
[2, 4]
);
# Turns the above into:
# [4, START, 1]
# [9, END, 1]
# [3, START, 2]
# [6, END, 2]
# [2, START, 3]
# [4, END, 3]
my ($counter, @encoded) = 1;
foreach my $item (@timeslices) {
push @encoded, [$item[0], START, $counter];
push @encoded, [$item[1], END, $counter++];
}
# Turns @encoded above into:
# [2, START, 3]
# [3, START, 2]
# [4, START, 1]
# [4, END, 3]
# [6, END, 2]
# [9, END, 1]
my @sorted = map { $_->[0] }
sort { $a->[0] <=> $b->[0] # Sort by element 0
||
$b->[1] <=> $b->[1] # then by element 1
}
@encoded;
# Keep track of beginning time and total
my $total = 0;
my $previous = 0;
my %active; # Active timeslots
# Loop:
# * If we get a START, add it to a hash
# * If we get an END, remove it from the hash
# * If the hash has something in it, then
# total += previous - current
#
foreach my $item (@sorted) {
# * If we get a START, add it to a hash
if ($item[0] == START) {
$active{$item[2]}++;
}
# * If we get an END, remove it from the hash
else {
delete $active{$item[2]};
}
# * If the hash has something in it, then
# total += previous - current
if (%active != 0) {
$total += $previous - $current;
}
}
print $total;
===================================================
There is a bug someplace that prevents it printing
the correct value - knowledgable people are welcome
to find it... I've no more time available just now.
I think this might be the fastest solution thus far.
Jonathan Paton
=====
$_=q|.,&@$$. ,.@$&@$. .&$$@. ,,$ ....!$_=$p.'&$@.',y'&$@' .,';for(/\S+/g){
!|.q| .$ .,@, ,$, .,.. @, ,$ ,,@ .,,.!++$.<22?${'y'.$_}=chr$.+64:[$$=${'y'
!|.q| ,@$@&.,. $$$&, ..@&&$,,, $., ..!.$_},$y.=($.=~/22\|26\|3(3\|7)/x?' '
!|.q|. @ ., ,.&,,, , .$..&. .,$ .,,!.$$:"\l$$")]};$y=~/ (.*)/;warn"$1\n"
!|.q|. $ .,. .,$$&&$...&., @.,.&@$@ .|,map{-$|--?$r:$p.=$_}split'!';eval$r
__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page
from News and Sport to Email and Music Charts
http://uk.my.yahoo.com
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
