3 ms·
PS: here is a quick and dirty Perl program to do it. I did not bother matching the output format exactly, as I just wanted to get the algorithm right. This shou
by tzs 10y ago
PS: here is a quick and dirty Perl program to do it. I did not bother matching the output format exactly, as I just wanted to get the algorithm right. This should be O(n log n) where n is the number of appointments, assuming that the built-in sort is O(n log n) and that the built-in hash implementation is O(n log n) or better.
my @appt = ([1, 5], [3, 7], [2, 6], [10, 15], [5, 6], [4, 100]);
my %active;
my @endpoints;
for (my $i = 0; $i < @appt; ++$i)
{
my($start, $end) = @{$appt[$i]};
push @endpoints, [$start, 1, $i];
push @endpoints, [$end, 0, $i];
}
@endpoints = sort {$a->[0]*2+$a->[1] <=> $b->[0]*2+$b->[1]} @endpoints;
foreach (@endpoints)
{
my($time, $side, $which) = @$_;
if ($side == 0) {
delete $active{$which};
} else {
print "$which overlaps $_\n" foreach sort {$a <=> $b} keys %active;
$active{$which} = 1;
}
}
Idea behind this: make list of all the appointment endpoints, tagged by whether they are a start or end time and which appointment they came from. Sort this by time, with end times coming ahead of start times if a given time occurs more than once. You can then scan this list, keeping track in a hash which appointments you have seen a start time for without yet seeing the corresponding end time.
When you see an end time, you can delete the appointment from the hash. When you see a start time, the appointment that supplied it overlaps with all the appointments currently in the hash.