# Is a merge interval function available?

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

I'm wondering there is already a function in perl library that can
merge intervals. For example, if I have the following intervals ('['
and ']' means closed interval as in
http://en.wikipedia.org/wiki/Interval_ (mathematics)#Excluding_the_endpoints)

[1, 3]
[2, 9]
[10,13]
[11,12]

I want to get the following merged intervals.

[1,9]
[10,13]

Could somebody let me know if there is a function in the perl library?

## Re: Is a merge interval function available?

A quick search of CPAN doesn't turn up anything obvious, but something
like this should work:

use 5.010;
use strict;
use warnings;

use List::Util qw/max/;

sub closed_cover {
my @in = sort {
\$a->[0] <=> \$b->[0] ||
\$a->[1] <=> \$b->[1]
} @_;

my \$last = shift @in;
my @out;

while (my \$next = shift @in) {
if (\$next->[0] <= \$last->[1]) {
\$last->[1] = max \$last->[1], \$next->[1];
}
else {
push @out, \$last;
\$last = \$next;
}
}

return @out, \$last;
}

say "[\$[0], \$[1]]" for closed_cover
[1, 3], [2, 9], [10, 13], [11, 12];

Ben

## Re: Is a merge interval function available?

Here's another way.

-sln

---------------
use strict;
use warnings;

my @sets = (
[20, 40],
[1, 3],
[2, 9],
[10,13],
[11,13],
[1, 2],
[11,12],
[1, 5],
);

my @merged_sets = interval(\@sets);

print "\nOriginal sets:\n";
for my \$st (@sets) {
if (@) {
printf "  %2s, %2s\n", @;
}
}
print "\nMerged sets:\n";
for my \$st (@merged_sets) {
if (@) {
printf "  %2s, %2s\n", @;
}
}
exit (0);

##
sub interval
{
my (\$sref,\$start) = @_;
return if (ref(\$sref) ne 'ARRAY');

if (!defined \$start) {
if (wantarray) {
my @tmpsets = map ]} @;
\$sref = \@tmpsets;
}
@ = sort {\$a->[0]<=>\$b->[0] || \$a->[1]<=>\$b->[1]} @;
\$start = 0;
}
my \$last = \$sref->[\$start];
++\$start;

if (@) {
for my \$ndx (\$start .. @-1)
{
my \$cur = \$sref->[\$ndx];
next if (!@);

if (\$cur->[0] >= \$last->[0] && \$cur->[0] <= \$last->[1] )
{
\$last->[1] = \$cur->[1] if (\$cur->[1] > \$last->[1]);
@ = ();
}
else {
last;
}
}
}
interval(\$sref, \$start) if ( \$start < @);
if (wantarray) {
return sort {\$a->[0] <=> \$b->[0]} map ? \$_ : () } @;
}
}

__END__

Output -

Original sets:
20, 40
1,  3
2,  9
10, 13
11, 13
1,  2
11, 12
1,  5

Merged sets:
1,  9
10, 13
20, 40

## Re: Is a merge interval function available?

Should be non-recursive, my bad.

-sln

-------------
use strict;
use warnings;

my @sets = (
[20, 40],
[1, 3],
[2, 9],
[10,13],
[11,13],
[1, 2],
[11,12],
[1, 5],
[7, 15],
);

my @merged_sets = mrgInterval(\@sets);

print "\nOriginal sets:\n";
for my \$st (@sets) {
if (@) {
printf "  %2s, %2s\n", @;
}
}
print "\nMerged sets:\n";
for my \$st (@merged_sets) {
printf "  %2s, %2s\n", @;
}
exit (0);

##
sub mrgInterval
{
my (\$sref,\$start) = @_;
return if (ref(\$sref) ne 'ARRAY');

if (!defined \$start) {
if (wantarray) {
my @tmpsets = map ]} @;
\$sref = \@tmpsets;
}
@ = sort {\$a->[0]<=>\$b->[0] || \$a->[1]<=>\$b->[1]} @;
\$start = 0;
}

while (\$start < @)
{
my \$last = \$sref->[\$start];
++\$start;

if (@) {
for my \$ndx (\$start .. @-1)
{
my \$cur = \$sref->[\$ndx];
next if (!@);

if (\$cur->[0] >= \$last->[0] && \$cur->[0] <= \$last->[1] )
{
if (\$cur->[1] > \$last->[1]) {
\$last->[1] = \$cur->[1];
}
@ = ();
}
else {
last;
}
}
}
}
if (wantarray) {
return sort {\$a->[0] <=> \$b->[0]} map ? \$_ : () } @;
}
}

__END__

Original sets:
20, 40
1,  3
2,  9
10, 13
11, 13
1,  2
11, 12
1,  5
7, 15

Merged sets:
1, 15
20, 40

## Re: Is a merge interval function available?

Peng Yu wrote:

Maybe CPAN is with you:  Set::Infinite, Set::IntSpan

br,
Josef