13
\$\begingroup\$

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)
\$\endgroup\$
  • 3
    \$\begingroup\$ Will the intervals always be sorted as they are in your examples? \$\endgroup\$ – Peter Olson Apr 21 '11 at 6:18
  • \$\begingroup\$ bounds on the numbers? \$\endgroup\$ – st0le Apr 21 '11 at 9:44
  • 1
    \$\begingroup\$ Why don't [2, 3], [4, 5] overlap, or [2, 4], [4, 5] either? They both yield 2345. \$\endgroup\$ – mellamokb Apr 21 '11 at 14:04
  • 2
    \$\begingroup\$ Are the intervals only on the set of integers? \$\endgroup\$ – Lowjacker Apr 21 '11 at 15:31
  • 1
    \$\begingroup\$ 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]? \$\endgroup\$ – MtnViewMark Apr 22 '11 at 2:42
2
\$\begingroup\$

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]]
\$\endgroup\$
4
\$\begingroup\$

Haskell (103)

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|x`elem`l=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]
\$\endgroup\$
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ perform the union of them should lead to (1,11) (13,18), shouldn't it? \$\endgroup\$ – user unknown Apr 21 '11 at 8:57
  • \$\begingroup\$ @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. \$\endgroup\$ – mellamokb Apr 21 '11 at 14:02
  • \$\begingroup\$ "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. \$\endgroup\$ – user unknown Apr 21 '11 at 14:53
  • \$\begingroup\$ @user unknown: I agree. That's why I've commented about it on the question. Hopefully the OP will respond :) \$\endgroup\$ – mellamokb Apr 21 '11 at 15:30
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 55 characters

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.

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

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))
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.