#!/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