I think a better data structure is the answer.

He should use DB_File with a BTREE and specify a custom sort order if it makes sense. In there he should put the times that he changes from inside to outside of any interval, and what he did. He can then use the OO interface, and use the seq method (with the R_CURSOR flag) to find the next action efficiently, and from that he can figure out his current state.

Here is example code demonstrating this that goes one step further. Note that the API I am coding to has some things I don't like (sorry, I don't like destructive methods) but I am more than willing to put up with it for the functionality provided: 

#!/usr/bin/perl -w
use strict;
use DB_File;

# The original data structure
my %interval = qw(
  5     50
  20    30
  70    90
  120   130
);

# The times
my @times = qw(4 9 30 98 125 500);

# Let us rearrange the interval information
# into events consisting of a time/action.
my @events = map {[$_, 1]} keys %interval;
push @events, map {[$_, -1]} values %interval;

# Let us turn this array into something we can
# do a fast lookup on...

# First we need a useful comparison order:
$DB_BTREE->{'compare'} = sub {$_[0] <=> $_[1]};
# Next we need a hash to store information in
my %interval_end;
tie(
  %interval_end, 'DB_File', undef,
  O_RDWR|O_CREAT, 0640, $DB_BTREE
) or die "Cannot tie hash: $!";

# Now store the information.
my $nesting = 0;
foreach my $event (sort {$a->[0] <=> $b->[0]} @events) {
  my ($time, $action) = @$event;
  # Careful, multiple intervals may share a boundary...
  unless (exists $interval_end{$time}) {
    $interval_end{$time} = $nesting;
  }
  $nesting += $action;
}

# Now we get the tied object so we can do our fast lookup.
my $interval_depth = tied %interval_end;
# And now let us get our answers:
foreach my $time (@times) {
  my $ended = $time;
  my $depth = 0;
  $interval_depth->seq($ended, $depth, R_CURSOR);
  print "$time is in an interval ending at $ended of depth $depth\n";
}
__END__
Output:
4 is in an interval ending at 5 of depth 0
9 is in an interval ending at 20 of depth 1
30 is in an interval ending at 30 of depth 2
98 is in an interval ending at 120 of depth 0
125 is in an interval ending at 130 of depth 1
500 is in an interval ending at 500 of depth 0

[download]
Note that the final entry gave a somewhat non-intuitive answer. And there could be more error checking. Plus all intervals have been made open on the left and closed on the right. But oh well.

(This should be efficient on his original data set.)

UPDATE
There is more than a little irony in my pointing out the capabilities of BTrees to Dominus. The first place that I heard of them was this article. (Which I enjoyed quite a bit.)

In reply to Re (tilly) 1: Assemble times into ranges by tilly
in thread Assemble times into ranges by Dominus

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.