Sprenger000 has asked for the wisdom of the Perl Monks concerning the following question:

This will probably seem like a Comp Sci exam question, but honestly it's a real problem I need to solve and it's driving me nuts.

I have a list of time ranges: pairs of numbers representing a starting time and an ending time. The list consists of an arbitrary number of elements the number of which is not controllable within the scope of the application. These numbers are in the general time format of HH:MM on a 24 hour scale.

I would like to determine what (if any) ranges of time are not included in any of the ranges denoted by the pairs in my list (within 0-24 hours).

As always, some code may help to visualize. For lack of anything more inspired we'll put the source data in an array structure: 

@array = (
  [ '03:30', '05:45' ],
  [ '05:45', '09:15' ],
  [ '10:00', '11:35' ],
  [ '11:00', '15:40' ]
);

[download]
Some assumptions about the data that will always be true:

(I feel that last one needs explaining: while 24:00 is not a real time, it's needed to indicate a "full" ending range. If a user wants to specify "11:00pm until Midnight" I can't use 00:00 since that's technically last midnight, and I don't want to force the user into specifying something like 23:59 since that leaves a small gap. So 24 is a way to indicate the full range of time up until midnight, whether that's 23:59 or 23:59.99999.)

The specific results I need from these are the ranges of time not included in any of the pairs in the list. In the example code from above, it would be nice to see a result set that looks like: 

(
  [ '00:00', '03:30' ],
  [ '09:15', '10:00' ],
  [ '15:40', '24:00' ]
);

[download]

Note that having two ranges back to back does NOT result in a "gap": the 3:30-5:45 and 5:45-9:15 ranges should be considered contiguous.

I just have no idea how to get this result from the previous sample data. I'd really like to avoid hacks like testing each minute in a 24 hour period, as that would probably not be performance-effective...

Any suggestions would be very much appreciated! I'm also open to changes on how the data is structured and formatted, if changes will help with possible solutions. Thanks!

Replies are listed 'Best First'.
Re: Determining gaps in time ranges
by kvale (Monsignor) on Apr 02, 2004 at 01:50 UTC
    When computing with integer ranges, Set::IntSpan is a useful module: 
    use Set::IntSpan;
use warnings;
use strict;

my $set_spec1 = '21-45';
my $set_spec2 = '44-60';

my $set = new Set::IntSpan $set_spec1;
my $u_set = union $set $set_spec2;
my $runlist = run_list $u_set ;
print $runlist;

    [download]
    This prints 21-60.

    Now, computiing integer ranges from your times (60*hour+ minute), you can combine ranges as above.

    -Mark

[reply]
[d/l]
[select]
Re: Determining gaps in time ranges
by BrowserUk (Patriarch) on Apr 02, 2004 at 01:44 UTC 

    #! perl -slw
use strict;
use Data::Dumper;

sub hm2mins{ 
    $_[ 0 ] =~ m[^(\d\d):(\d\d)$] and return $1 * 60 + $2;
}
sub mins2hm{ 
    sprintf '%02d:%02d',  int( $_[ 0 ] / 60 ), $_[ 0 ] % 60  ;
}

my @HM = (
  [ '03:30', '05:45' ],
  [ '05:45', '09:15' ],
  [ '10:00', '11:35' ],
  [ '11:00', '15:40' ]
);

my $stick = '0' x ( 60 * 24 );

for ( @HM ) {
    my( $start, $stop )  = ( hm2mins( $_->[ 0 ] ), hm2mins( $_->[ 1 ] 
+) );
    substr( $stick, $start, $stop - $start ) = '1' x ( $stop - $start)
+;
}

my @out;
push @out, [ pos( $stick ), length $1 ] while $stick =~ m[(0+)]g;

@out = map{ 
    my $start = $_->[ 0 ] -  $_->[ 1 ];
    my $stop = $_->[ 0 ];
    [ mins2hm( $start ), mins2hm( $stop ) ]
} @out;

print Dumper \@out;

__END__
P:\test>341852
$VAR1 = [
          [
            '00:00',
            '03:30'
          ],
          [
            '09:15',
            '10:00'
          ],
          [
            '15:40',
            '24:00'
          ]
        ];

    [download]
    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
[reply]
[d/l]

      Or TIMTOWDI 

      my @array = (
  [ '03:30', '05:45' ],
  [ '05:45', '09:15' ],
  [ '10:00', '11:35' ],
  [ '11:00', '15:40' ]
);

sub hhmm2min {
    die "Data error $_[0] not in format HH:MM\n" unless $_[0] =~ m/(\d
+\d):(\d\d)/;
  return $1*60+$2;
}

sub min2hhmm {
    die "Data error $_[0] > 24:00\n" if $_[0] > 24*60;
  return sprintf "%02d:%02d", int($_[0]/60), $_[0]%60;
}

@array = sort{ $a->[0]<=>$b->[0] }map{ [ hhmm2min($_->[0]), hhmm2min($
+_->[1]) ] }@array;
my $cur = 0;
my @missing = ();
for my $r( @array ) {
    push @missing, [ min2hhmm($cur), min2hhmm( $r->[0] ) ] if $cur < $
+r->[0];
    #$cur = $r->[1]; # bug
    $cur = $r->[1] unless $cur > $r->[1];
}
push @missing, [ min2hhmm($cur), '24:00' ] unless $cur == 24*60;

use Data::Dumper;
print Dumper \@missing;

__DATA__
$VAR1 = [
          [
            '00:00',
            '03:30'
          ],
          [
            '09:15',
            '10:00'
          ],
          [
            '15:40',
            '24:00'
          ]
        ];

      [download]

      cheers

      tachyon

[reply]
[d/l]
        tachyon's code, as well as the other suggestions, works very well (and is plenty efficient for my needs). Much thanks guys!
[reply]
Re: Determining gaps in time ranges
by PodMaster (Abbot) on Apr 02, 2004 at 02:34 UTC
[reply]
Re: Determining gaps in time ranges
by davido (Cardinal) on Apr 02, 2004 at 01:36 UTC
    I think you should have a look at the Date::Range module. After reading its POD, it looks like, in particular, the gap() method is almost exactly what you're looking for. You may have to massage your input data into a format understood by Date::Range, but that shouldn't be too hard.

    I hope this helps...Good luck!

    Update: Ugg! It looks like I jumped the gun; this would be an excellent solution for ranges of dates, but doesn't appear to deal with time-resolution. Sorry! ;)


    Dave

[reply]
[d/l]
Re: Determining gaps in time ranges
by fglock (Vicar) on Apr 02, 2004 at 21:10 UTC

    If you could translate ':' to '.', you could use:

      use strict;
  use Set::Infinite;

  my @array = (
      [ '03.30', '05.45' ],
      [ '05.45', '09.15' ],
      [ '10.00', '11.35' ],
      [ '11.00', '15.40' ]
    );

  my $set = Set::Infinite->new;

  $set = $set->union( $_ ) for @array;

  print "intervals: $set\n";

  my $gaps = $set->complement->intersection( '00.00' , '24.00' );

  print "gaps: $gaps\n";

# intervals: [03.30..09.15],[10.00..15.40]
# gaps: [00.00..03.30),(09.15..10.00),(15.40..24.00]

    [download]

    update: tested.

[reply]
[d/l]

Back to Seekers of Perl Wisdom