# Union of Intervals

Given a list of intervals, perform the union of them, and reduce overlaps. That means, overlapping parts are reduced. ([a, b] U [c, d] = [a, d] if b > c) Assuming all a < b in all intervals [a, b]. Implement as a function of a list of input intervals -> list of output intervals. Shortest code wins. You cannot use any existing libraries.

Clarifications:

• Open and closed intervals are not distinguished.
• Intervals for real numbers, not integers. ([2, 3], [4, 5] -> [2, 3], [4, 5])
• No need to sort output intervals
• The order if inputs do not matter
• Illegal inputs are only [a, b] where b >= a, it has nothing to do with the order of input intervals and the number of input intervals.
• You do not need to show an error message on undefined behaviors

Examples (with number lines)

 [2, 4], [7, 9] --> [2, 4], [7, 9]
234
789
-> 234  789

[1, 5], [2, 10] --> [1, 10] (overlapping [2, 5] reduced)

12345
234567890
-> 1234567890
[2, 4], [3, 6], [8, 9] -> [2, 6], [8, 9]
234
3456
89
-> 23456 89

[4, 2], [2, 2] -> (undefined behavior: against the assumption)

• Will the intervals always be sorted as they are in your examples? – Peter Olson Apr 21 '11 at 6:18
• bounds on the numbers? – st0le Apr 21 '11 at 9:44
• Why don't [2, 3], [4, 5] overlap, or [2, 4], [4, 5] either? They both yield 2345. – mellamokb Apr 21 '11 at 14:04
• Are the intervals only on the set of integers? – Lowjacker Apr 21 '11 at 15:31
• We need some clarification: 1) Is [4,5],[1,2] legal input? 2) Should the output of [2,3],[4,5] be [2,5] or [2,3],[4,5]? 3) Should the output of [2,3],[3,4] be [2,4] or [2,3],[3,4]? – MtnViewMark Apr 22 '11 at 2:42

# GolfScript, 32

[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]  • Add 2 characters if you prefer a block, 4 if you prefer a named block. • Input and output are array of pairs, e.g. [[2 4] [3 5]] • Assumes that input is ordered by the first element. • Compacts "adjacent" ranges ([2 4][5 6] -> [2 6]) • First GolfScript effort. Advice & rotten fruit appreciated. Full test program: [~](;2/[{1$1$*-2%~2->{*$[(\)\;]}{}if}*]


Example invocation:

ruby golfscript.rb intervals.gs <<EOF
3
2 4
3 6
8 9
EOF
# Expected output: [[2 6] [8 9]]


I think, it is way too verbose for Haskell. Thanks to Hoa Long Tam for his sorting function.

m%(x:y)|x>m=m:x:y|2>1=x:m%y;m%_=[m]
(x:y)?l|xeleml=y?l|0<1=x:y?(x:l);a?_=a
a∪b=foldr(%)[](a++b)?[]


In Haskell, an intervall from a to b is denoted by [a..b]. My notation is very similar to the mathematical notation. Use it like this:

[a..b] ∪ [c..d] ∪ ... ∪ [y..z]


Ok, here's my 250 character crack at it.

void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}


The function takes an int array, and operates on it in-situ. The array is terminated by a 0, and the intervals may be given in any order.

Sample output:

input list: (7,9) (5,6) (1,4) (15,18) (13,16) (2,3) (8,11)
output list: (1,4) (5,6) (7,11) (13,18)


Sample program:

#include <stdio.h>

void n(int a[]){if(!a[2])return;if(a[2]<=a[1]){if(a[1]<a[3])a[1]=a[3];
int *b=a+2;while(*b=*(b+2))++b;n(a);}n(a+2);}
void m(int a[]){if(!a[2])return;if(a[0]>a[2]){int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;a[1]=a[3];a[3]=t;m(a+2);m(a);n(a);}m(a+2);n(a+2);}

/*
void n(int a[])
{
if(!a[2])return;
if(a[2]<=a[1]) {
if(a[1]<a[3])
a[1]=a[3];
int *b=a+2;
while(*b=*(b+2))++b;
n(a);
}
n(a+2);
}

void m(int a[])
{
if(!a[2])return;
if(a[0]>a[2]) {
int s=a[0],t=a[1];
a[0]=a[2];a[2]=s;
a[1]=a[3];a[3]=t;
m(a+2);m(a);n(a);
}
m(a+2);n(a+2);
}
*/

void p(int a[])
{
if(!*a) {
printf("\n");
return;
}
printf("(%d,%d) ",a[0],a[1]);
p(a+2);
}

int main (int argc, const char * argv[])
{
// Code golf entry
// Interval Merging

int a[] = {7,9,5,6,1,4,15,18,13,16,2,3,8,11,0};
printf( "input list: " ); p(a);
m(a);
printf( "output list: " ); p(a);

return 0;
}

• perform the union of them should lead to (1,11) (13,18), shouldn't it? – user unknown Apr 21 '11 at 8:57
• @user unknown: I would have thought the same thing, but I guess the instructions say only combine if they overlap. So (1, 4) (5, 6) are not combined according to the rule ([a, b] U [c, d] = [a, d] if b > c). And for that matter, even (1, 5) (5, 6) would not be combined. – mellamokb Apr 21 '11 at 14:02
• "Given a list of intervals, perform the union of them, and reduce overlaps" and reduce overlaps - not if they overlap. OK - the following that means ... points again in the opposite direction. – user unknown Apr 21 '11 at 14:53
• @user unknown: I agree. That's why I've commented about it on the question. Hopefully the OP will respond :) – mellamokb Apr 21 '11 at 15:30

## Python, 100 chars

def f(L):R=sorted(set(p for p in sum(L,[])if 1-any(x<p<y for x,y in L)));return zip(R[::2],R[1::2])
print f([[2, 4], [7, 9]])
print f([[1, 5], [2, 10]])
print f([[3, 6], [2, 4], [8, 9]])
print f([[1, 5], [3, 5], [4, 5]])


generates

[(2, 4), (7, 9)]
[(1, 10)]
[(2, 6), (8, 9)]
[(1, 5)]


Takes all the endpoints of the intervals, removes any that are strictly inside another interval, uniquifies & sorts them, and pairs them up.

v(q@(a,b):p@(c,d):r)|c>b=q:v(p:r)|1<3=v((a,d):r);v x=x


If the input is unsorted, then 88 characters:

p@(a,b)§(q@(c,d):r)|b<c=p:q§r|a>d=q:p§r|1<3=(min a c,max b d)§r;p§_=[p]
u i=foldr(§)[]i


Test runs:

ghci> testAll v
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]
ghci> testAll u
pass: [(2,4),(7,9)] --> [(2,4),(7,9)]
pass: [(1,5),(2,10)] --> [(1,10)]
pass: [(2,4),(3,6),(8,9)] --> [(2,6),(8,9)]


I'm assuming that "can't use any existing libraries" precludes importing List and calling sort. If that were legal, than the unsorted version would be only 71 characters.

• importing List from package Haskell98 would be sufficient IMHO. – FUZxxl Apr 22 '11 at 11:25

## Scala, 272 characters

type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}


Usage:

object Intervals2 extends Application
{
type p=List[(Int,Int)];def f(l:p):p={var(a,s,c,o)=(new Array[Int]((l map(x=>x._2)max)+1),0,0,List[Int]());l map(x=>(a(x._1)+=1,a(x._2)-=1));while(c<a.size){s+=a(c);if(a(c)==1&&s==1)o=o:+c;if(a(c)== -1&&s==0)o=o:+c;c+=1};return(o.grouped(2).map(x=>(x.head,x.last)).toList)}

print(f(List((1,2),(3,7),(4,10))))
}


Creates an array and inserts a 1 for every interval start and a -1 for every interval end. Then steps through the array adding the values to a counter outputting a start every time the counter steps from 0 to 1 and an end when it steps from 1 to 0. Probably unnecessarily complicated.

Output:

List((1,2), (3,10))


## Perl (146)(92) (90)

golfed down to 90 chars, creatively using the regex engine

sub u{map$h[$_]=1,@$_[0]..@$_[1]for@_;$w.=$_+0for@h;push@r,$-[0],$+[0]-1while$w=~/1+/g;@r}  usage example: my @out1 = u([1, 5], [2, 10]); # (1,10) my @out2 = u([2, 4], [3, 6], [8, 9]); # (2, 6, 8, 9)  let's explain this code a bit. this subroutine receives an array of arrayrefs, each aref pointing to an array containing two elements, start and end of the interval: ([2, 4], [3, 6], [8, 9]) for every aref, we generate an array of elements from first to last ($_->[0] .. $_->[1]). then we use map to set elements of such indexes in @h to 1. for (@_) { map {$h[$_] = 1} ($_->[0] .. $_->[1]); }  after this, @h will contain either ones (for intervals) or undefs, depicted below as hyphens for clarity. index: 0 1 2 3 4 5 6 7 8 9 @h: - - 1 1 1 1 1 - 1 1  next we build a string from @h, adding 0 to replace undefs with something more useful (undef + 0 = 0). $w .= $_+0 for @h;$w contains 011111011 now.

it's time to abuse the regex engine a bit.

push @r, ($-[0],$+[0]-1) while $w=~/1+/g; after successful matches, @- and @+ arrays contain respectively position of start and end of each match; 0th element is used for the entire match, first for$1, second for $2 and so on. $+[0] actually contains the position of first non-matching char, so we have to substract one.

@r contains (2, 6, 8, 9) now.

@r

to make the sub return @r.

### Scala 305 279 chars without invocation:

type I=(Int,Int)
def l(p:I,q:I)=if(p._1<q._1)true else if(p._1>q._1)false else p._2<q._2
def r(l:List[I]):List[I]=l match{case x::y::z=>{if(y._1<=x._2&&y._2>x._2)(x._1,y._2)::r(z)else
if(y._1<=x._2&&y._2<=x._2)x::r(z)else
x::r(y::z)}case _=>l}
def c(v:List[I])=r(v.sortWith(l))


invocation:

val i=List((7,9),(5,6),(1,4),(15,18),(13,16),(2,3),(8,11))
c(i)
res0: List[(Int, Int)] = List((1,4), (5,6), (7,11), (13,18))
`