> 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]