Hi
I have been looking back at this problem and here is what I have found.
Lets take the following set of times
A , B
1 (4 , 5)
2 (9 , 10)
3 (11 , 12)
4 (12 , 14)
5 (12 , 18)
6 (14 , 15)
If we sort by column A the set inherits the following property or Rule
a1 <= a2 is always true
This means that we are only interested b1 properties in relation to a2 and
b2. If (b1 >= b2) then because of Rule 1 we can ignore the values in the
second set and remove them.
If this is not the case then if (b1 < a2) we can safely deduce that it has
no overlap in any other set from rule 1 and calculate the time and store it.
If however (b1 < a2) is false then because of Rule 1 we can safely replace
b1 with b2 and remove the second set.
The code I have used to get the results is at the end. I have no idea if it
is a fast solution. I am not sure if it is the best way to code it either
and I am sure some people can optimise it for best performance. I wanted to
use a for loop but went for the easier while loop instead.
__BEGIN__
#!/usr/bin/perl -w
use warnings;
use strict;
my @startstop = (
[1, 2],
[3, 6],
[4, 9],
[0, 2],
[4, 9],
[5, 6],
[7, 10],
[15, 16],
[18, 19]
);
my $total = 0;
# Sort the array on column A
#
@startstop = sort { $a->[0] <=> $b->[0]} @startstop;
# LOOP UNTIL NO MORE ENTRIES IN ARRAY.
while (@startstop){
print "". @{@startstop->[0]}->[0].",".@{@startstop->[0]}->[1]."\t
".@startstop."\t\tTot = $total\n";
if (@startstop eq 1) {
$total += ( (@{@startstop->[0]}->[1]) - (@{@startstop->[0]}->[0] )
);
shift (@startstop);
next;
}
if (@{@startstop->[0]}->[1] >= @{@startstop->[1]}->[1]) {
splice (@{@startstop},1,1);
next;
}
if (@{@startstop->[0]}->[1] < @{@startstop->[1]}->[0]) {
$total = $total + ( (@{@startstop->[0]}->[1]) -
(@{@startstop->[0]}->[0] ) );
shift (@startstop);
next;
}
else {
@{@startstop->[1]}->[0] = @{@startstop->[0]}->[0];
shift (@startstop);
next;
}
}
print "$total\n";
__END__
Some other considerations that may have to be considered if it is going to
become a module.
For thousands of records if we find the greatest stop time then if our
searching set every has this value as its stop time we can calculate the
total and exit without iterating over any more sets providing the set has
been sorted on column A.
When we have sets with matching start times we are only interested in the
set with the largest difference and vice versa for the stop times.
I have also tried to make it work on negative times, i.e.
If you could start before your official start time it may come out as a
negative number in a clocking in machine. This will not be the case for
timestamps though.
Any though on the above code appreciated.
Harry
*************************************************************************************
COLT Telecommunications
Registered in England No. 2452736
Registered Office: Bishopsgate Court, 4 Norton Folgate, London E1 6DQ
Tel. +44 20 7390 3900
This message is subject to and does not create or vary any contractual
relationship between COLT Telecommunications, its subsidiaries or
affiliates ("COLT") and you. Internet communications are not secure
and therefore COLT does not accept legal responsibility for the
contents of this message. Any view or opinions expressed are those of
the author. The message is intended for the addressee only and its
contents and any attached files are strictly confidential. If you have
received it in error, please telephone the number above. Thank you.
*************************************************************************************
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
