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.