It's not clear to me what you mean by "generalise", but this simplifies it a little, and appears to produce similar output for the test case:

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

my %in;
m[(\d\d):\d\d (.+)$] and push @{ $in{ $1 } }, $2 while <DATA>;

for my $hr ( sort{ $a <=> $b } keys %in ) {
    my $n = $#{ $in{ $hr } };
    my $step = 60 / $n;
    my $min = 0;
    for my $flight ( @{ $in{ $hr } } ) {
        printf( "%02d:%02d %s\n", $hr, int( $min ), $flight );
        $min += $step;
        $min = 59 if $min > 59;
    }
}

__DATA__
11:10 A1
11:30 E4
11:30 Z4
11:50 H5
12:02 H6
12:25 B2
12:25 A8
12:30 F3
12:30 E7
12:50 E15
12:55 E16
[download]

Produces:

C:\test>725886.pl
11:00 A1
11:20 E4
11:40 Z4
11:59 H5
12:00 H6
12:10 B2
12:20 A8
12:30 F3
12:40 E7
12:50 E15
12:59 E16
[download]