Discussion on: Remove terrible bus routes (find an algorithm)

#! /usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

<>; # Ignore the size, just process all the lines.

my @good;
while (<>) {
    my ($leave, $arrive) = split;

    # Binary search.
    my ($from, $to) = (0, $#good);
    while ($from < $to) {
        my $middle = int(($from + $to) / 2);
        if ($good[$middle][0] < $leave) {
            $from = $middle + 1;
        } else {
            $to = $middle;
        }
    }
    my $new = $from + (@good && $good[-1][0] < $leave);

    if ($new < $#good && $good[$new][0] == $leave) {
        $good[$new][1] = $arrive if $arrive < $good[$new][1];
        next
    }

    if ($new > $#good || $arrive < $good[$new][1]) {
        splice @good, $new, 0, [$leave, $arrive];

        if ($new) {
            my $before = $new;
            do { --$before } while $before && $good[$before][1] >= $arrive;
            splice @good, $before + 1, $new - $before - 1;
        }
    }
}

say scalar @good;
say "@$_" for @good;