Task — Measuring the gaps

We are given a list of at least 2 times in the 24-hour format HH:MM and are asked to write a script to find out the shortest time in minutes between any two time points, which may not be in the same day.

Analysis

There are two slightly awkward aspects to this task. The first is that if we take any pair of times, the second could be either earlier or later than the first. The second issue is that if the pair are apparently more than 12 hours apart, then there will be a shorter gap between them that bridges midnight.

I therefore took two steps before examinig the list in detail. The first is to sort @time. Ignoring the midnight issue for now, the shortest gap is now going to be between two consecutive members of the list, with the second of those always larger - ie later - than the first.

The second step is to add another element at the end of @time which is 24 hours later than the (sorted) first element. It won't look like a proper time - for example it might be 27:15, but that's ok.

So now it's simply a case of looping over @time and finding the shortest increment between two consecutive members (and if you find a zero, you can stop looking).

You could claim that sorting a list is expensive and that you could do the task more economically with two nested loops to test each pair, and if the difference is > 720 minutes (12 hours) then use (1440 - difference) to cope with the midnight issue.

It's hard to test that claim, as there are only 24 * 60 = 1440 possible times, and a list containing all 1440 with no duplicates takes hardly any time with either my algorithm or the nested loops, so I'm sticking with my method.

Try it 

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2023-02-20

use v5.28;
use utf8;
use warnings;

# Task: You are given a list of time points, at least 2, in the 24-hour clock format HH:MM. Write a script 
# to find out the shortest time in minutes between any two time points.

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge/206/1

my (@time, $j);

shortest_interval("00:01", "01:05", "01:12", "23:59");
shortest_interval("01:01", "00:50", "00:57");
shortest_interval("10:10", "09:30", "09:00", "09:55");
shortest_interval("08:59", "21:00");
shortest_interval("09:01", "21:00");

for $j (0 .. 20) {
    @time[$j] = sprintf('%02d:%02d', rand(24), rand(60));
}
shortest_interval(@time);

sub shortest_interval {
    
    my (@times, $minutes, $shortest, $j, $gap, $this_minutes);
    
    # sort the times so that the shortest gap is bewteen 2 consecutive entries
    @times = sort @_;
    
    # add one to the end that is 24hr after the first, in case the shortest bridges midnight
    $times[0] =~ m|^(\d\d).(\d\d)|;
    $times[scalar(@times)] = sprintf('%02d:%02d', $1 + 24, $2);
    $minutes = $1 * 60 + $2;
    
    # pass along the list comparing each element with the previous one
    $shortest = 9999;
    for $j (1 .. scalar(@times) - 1) {
        $times[$j] =~ m|^(\d\d).(\d\d)|;
        $this_minutes = $1 * 60 + $2;
        $gap = $this_minutes - $minutes;
        $shortest = $gap if $gap < $shortest;
        last if $shortest == 0;
        $minutes = $this_minutes;
    }
    
    say qq[\nInput:  \@time = ("] . join('", "', @_) . qq[")\nOutput: $shortest];
}

Output

Input:  @time = ("00:01", "01:05", "01:12", "23:59")
Output: 2

Input:  @time = ("01:01", "00:50", "00:57")
Output: 4

Input:  @time = ("10:10", "09:30", "09:00", "09:55")
Output: 15

Input:  @time = ("08:59", "21:00")
Output: 719

Input:  @time = ("09:01", "21:00")
Output: 719

Input:  @time = ("06:22", "19:10", "08:32", "11:52", "06:29", "23:13", "14:10", "20:13", "09:34", "11:15", "00:28", "23:28", "12:32", "04:04", "19:07", "20:39", "09:51", "19:34", "16:12", "18:10", "12:47")
Output: 3