There is a trick to manage unicode sequences by storing where a sequence starts and then again where it stops. You can employ this trick here as well. If you look at all your numbers in order, you'll find that you start a sequence at the first number, then count up until you reach the next number, then start again with the next number and so on:

23    900   8000  10000 ...
start stop  start stop  ...
[download]

The thing to realize is that the inverted sequence (which you want) is constructed by simply prepending a 0 to that list:

      23    900   8000  10000 ...
      start stop  start stop  ...
0     23    900   8000  10000 ...
start stop  start stop  start ...
[download]

The only thing you still need to know about is whether the boundaries should be included in your list or not. From your description above, it seems that the list should start with 901 again, so you'll have to adjust the end markers for the first list (and thus the start markers for the inverse) by +1:

      23    901   8001  10001 ...
      start stop  start stop  ...
0     23    901   8001  10001 ...
start stop  start stop  start ...
[download]

Writing the code for this is left as an exercise to the reader.

I learned this trick from demerphq as a good trick how to implement the (vast) unicode character ranges, together with quick inversion.

Update: moritz found an earlier mention of the concept described by IBM at Cultured Perl: Inversion lists with Perl. The technical term seems to be "inversion lists", and there is Algorithm::InversionList, which implements the concept. The original interest in the data structure is attributed there to Unicode as well.

Ingenious.

It's possible to deal with overlapping regions fairly easily, on top of this algorithm. Once you have your initial inversion list, and you've adjusted your boundaries, just remove any resulting ranges which are "back to front".

Eg (for a complete range of 0-20):
input: (4-12), (8-16)
initial inversion:(0-4), (12-8), (16-20)
tweak boundaries:(0-3), (13-7), (17-20)
remove back-to-fronts:(0-3), (17-20)

Writing the code is (once again) left as an exercise for the reader (or an instruction to a minion, as applicable).

--
use JAPH;
print JAPH::asString();

use Bit::Vector;
use strict;
use warnings;

my $vector = Bit::Vector->new(1_000_000_000);
$vector->Fill();

my @ranges = ([39887, 399900],
              [23,    900],
              [8000,  10000],
              [50000, 1000500]);

$vector->Interval_Empty($_->[0] - 1, $_->[1] - 1) for @ranges;

my $start = 0;
while ($start < $vector->Size()
       and my ($min, $max) = $vector->Interval_Scan_inc($start))
{
    print(($min+1), "-", ($max+1), "\n");
    $start = $max + 2;
}
[download]

Prints:

$ perl bits.pl 
1-22
901-7999
10001-39886
1000501-1000000000
[download]

You might also look at Bit::Vector's to_Enum() and from_Enum() method, which do IO using ranges of indexes but it in a slightly different format from yours.

-sam

Hi, along Corion's suggestion but with a little bit of naive range-merging. HTH, although it looks a little bit C-ish...

use strict;
use warnings;

# valid ranges: 0..$max_line
my @err_ranges = qw(39887-399900 23-900 8000-10000 50000-1000500 40000
+-90000);
my $max_line   = 100000000;

# save b(egin) and e(nd) of ranges and sort by lower b(egin) of ranges
my @errs_b_e  = sort { $a->[0] <=> $b->[0] } map { m/(\d+)\-(\d+)/; [ 
+$1 , $2 ] } @err_ranges;

# merge overlapping and adjacent ranges
for (my $i=0; $i<$#errs_b_e; $i++) {
  my $cmp_a = $errs_b_e[$i];
  my $cmp_b = $errs_b_e[$i+1];
  my ($a_lo, $a_hi, $b_lo, $b_hi) = map { ($_->[0], $_->[1]) } ($cmp_a
+, $cmp_b);

  #overlapping? e.g. 10..20 15..25 --> 10..25
  if ($a_lo <= $b_lo and $b_lo <= $a_hi) {
    $cmp_b->[0] = $a_lo;         # lower bound defined by $a_lo
    $cmp_b->[1] = $a_hi > $b_hi ? $a_hi : $b_hi; # upper bound defined
+ by max.
    $cmp_a->[0] = -1             # taint LHS range
  } elsif ($a_hi == $b_lo-1) {   #adjacent? e.g. 10..20 21..22 --> 10.
+.22
    $cmp_b->[0] = $a_lo;         # lower bound defined by $a_lo
    $cmp_a->[0] = -1             # taint LHS range
  } #update/hint: the if/elsif above can be reduced ;-)
}

# remove tainted ranges, create list of inverse boundaries
my @merged =  map { $_->[0]-1 => $_->[1]+1 }  grep { $_->[0] >= 0 } @e
+rrs_b_e;

# edge-cases
$merged[0]  < 0          ?  shift @merged : unshift @merged, 0;
$merged[-1] > $max_line  ?  pop   @merged : push    @merged, $max_line
+;

for (my $i=0; $i<@merged; $i+=2) {
  print $merged[$i], "-", $merged[$i+1], "\n";
}
[download]

pb> perl 752436.pl
0-22
901-7999
10001-39886
1000501-100000000
[download]

my $max = 100000000;
my @list = (
    [ 39887, 399900 ],
    [ 23, 900 ],
    [ 8000, 10000 ],
    [ 50000, 1000500 ],
);

###

@list = sort { $a->[0] <=> $b->[0] } @list;

@res = (0);
$last = shift @list;

for (@list) {
    if ($_->[0] > $last->[1] + 1) {
        push @res, $last->[0] - 1, $last->[1] + 1;
        $last = $_;
    } else {
        $last->[1] = $_->[1] if $_->[1] > $last->[1];
    }
}

push @res, $last->[0] - 1, $last->[1] + 1;

$res->[-1] < $max ? push @res, $max : pop @res;

for (0 .. $#res) {
    print $res[$_], $_ % 2 ? "\n" : '-';
}
[download]