Compute the superset

Question

Your task here is simple:

Given a list of integer sets, find the set union. In other words, find the shortest list of integer sets that contain all the elements in the original list of sets (but no other elements). For example:

[1,5] and [3,9] becomes [1,9] as it contains all of the elements in both [1,5] and [3,9]
[1,3] and [5,9] stays as [1,3] and [5,9], because you don't want to include 4

Sets are notated using range notation: [1,4] means the integers 1,2,3,4. Sets can also be unbounded: [3,] means all of the integers >= 3, and [,-1] means all of the integers <= -1. It is guaranteed that the first element of the range will not be greater than the second.

You can choose to take sets in string notation, or you can use 2-element tuples, using a constant non-integer as the "infinite" value. You can use two distinct constants to represent the infinite upper bound and the infinite lower bound. For example, in Javascript, you could use [3,{}] to notate all integers >= 3, as long as you consistently used {} across all test cases.

Test cases:

[1,3]                     => [1,3]
[1,]                      => [1,]
[,9]                      => [,9]
[,]                       => [,]
[1,3],[4,9]               => [1,9]
[1,5],[8,9]               => [1,5],[8,9]
[1,5],[1,5]               => [1,5]
[1,5],[3,7]               => [1,7]
[-10,7],[1,5]             => [-10,7]
[1,1],[2,2],[3,3]         => [1,3]
[3,7],[1,5]               => [1,7]
[1,4],[8,]                => [1,4],[8,]
[1,4],[-1,]               => [-1,]
[1,4],[,5]                => [,5]
[1,4],[,-10]              => [1,4],[,-10]
[1,4],[,]                 => [,]
[1,4],[3,7],[8,9],[11,20] => [1,9],[11,20]

This is code-golf, so make your answer as short as possible!

Answer 1

R + intervals, 90 87 81 bytes

function(...)t(reduce(Intervals(rbind(...),type="Z")))+c(1,-1)
library(intervals)

Try it online!

Input is a list of intervals. -Inf and Inf are R built-ins for minus/plus infinity. Output is a matrix of columns of intervals.

Not usually a fan of using non-standard libraries but this one was fun. TIO doesn't have intervals installed. You can try it on your own installation or at https://rdrr.io/snippets/

The intervals package supports real and integer (type = "Z") intervals and the reduce function is a built-in for what the challenge wants, but the output seems to default to open intervals, so close_intervals +c(1,-1) is needed to get the desired result.

Old version had examples in list of lists which might be convenient so I've left the link here.

Answer 2

JavaScript (ES6), 103 bytes

Saved 1 byte thanks to @Shaggy
Saved 1 byte thanks to @KevinCruijssen

Expects +/-Infinity for infinite values.

a=>(a.sort(([p],[P])=>p-P).map(m=M=([p,q])=>p<M+2?M=q>M?q:M:(b.push([m,M]),m=p,M=q),b=[]),b[0]=[m,M],b)

Try it online!

How?

We first sort the intervals by their lower bound, from lowest to highest. Upper bounds are ignored.

We then iterate over the sorted intervals \$[p_n,q_n]\$, while keeping track of the current lower and upper bounds \$m\$ and \$M\$, initialized to \$p_1\$ and \$q_1\$ respectively.

For each interval \$[p_n,q_n]\$:

• If \$p_n\le M+1\$: this interval can be merged with the previous ones. But we may have a new upper bound, so we update \$M\$ to \$\max(M,q_n)\$.
• Otherwise: there is a gap between the previous intervals and this one. We create a new interval \$[m,M]\$ and update \$m\$ and \$M\$ to \$p_n\$ and \$q_n\$ respectively.

At the end of the process, we create a last interval with the current bounds \$[m,M]\$.

Commented

a => (                  // a[] = input array
  a.sort(([p], [P]) =>  // sort the intervals by their lower bound; we do not care about
    p - P)              // the upper bounds for now
  .map(m = M =          // initialize m and M to non-numeric values
    ([p, q]) =>         // for each interval [p, q] in a[]:
    p < M + 2 ?         //   if M is a number and p is less than or equal to M + 1:
      M = q > M ? q : M //     update the maximum M to max(M, q)
    : (                 //   else (we've found a gap, or this is the 1st iteration):
      b.push([m, M]),   //     push the interval [m, M] in b[]
      m = p,            //     update the minimum m to p
      M = q             //     update the maximum M to q
    ),                  //
    b = []              //   start with b[] = empty array
  ),                    // end of map()
  b[0] = [m, M], b      // overwrite the 1st entry of b[] with the last interval [m, M]
)                       // and return the final result

Answer 3

Python 2, 118 113 112 111 106 105 104 101 bytes

x=input()
x.sort();a=[];b,c=x[0]
for l,r in x:
 if l>c+1:a+=(b,c),;b,c=l,r
 c=max(c,r)
print[(b,c)]+a

Saved one byte thanks to Mr.Xcoder, one thanks to Jonathan Frech, and three thanks to Dead Possum.
Try it online!

Answer 4

Ruby, 89 76 bytes

->a{[*a.sort.reduce{|s,y|s+=y;y[0]-s[-3]<2&&s[-3,3]=s.max;s}.each_slice(2)]}

Try it online!

Sort the array, then flatten by appending all the ranges to the first: if a range overlaps the previous one, discard 2 elements from the last 3 (keeping only the max).

Unflatten everything at the end.

Answer 5

Stax, 46 39 38 bytes

├&P◙╛╛ΘΩ¿σa○♦◘♣┐¬≥∩ó¬îî◙k]∙♣•╘○π≡¡jN<♀

Run and debug it

This program takes input in the originally specified string notation.

Answer 6

Pascal (FPC), 367 362 357 bytes

uses math;type r=record a,b:real end;procedure d(a:array of r);var i,j:word;t:r;begin for i:=0to length(a)-1do for j:=0to i do if a[i].a<a[j].a then begin t:=a[i];a[i]:=a[j];a[j]:=t;end;j:=0;for i:=1to length(a)-1do if a[j].b>=a[i].a-1then begin a[j].a:=min(a[i].a,a[j].a);a[j].b:=max(a[i].b,a[j].b)end else j:=j+1;for i:=0to j do writeln(a[i].a,a[i].b)end;

Try it online!

A procedure that takes a dynamic array of records consisting of 2 range bounds, modifies the array in place and then writes it on standard output, one range per line. (Sorry for that twisted sentence.) Uses 1/0 for ubounded up and -1/0 for unbounded down.

Readable version

It would be nice to just return the array with corrected number of elements, but the dynamic array passed to function/procedure is not dynamic array anymore... First I found this, then there is this excellent, mind-boggling explanation.

This is the best data structure I could found for shortening the code. If you have better options, feel free to make a suggestion.

Answer 7

Wolfram Language (Mathematica), 57 bytes

List@@(#-{0,1}&/@IntervalUnion@@(Interval[#+{0,1}]&/@#))&

Try it online!

Takes input as a list of lists {a,b} representing the interval [a,b], where a can be -Infinity and b can be Infinity.

Uses the built-in IntervalUnion, but of course we have to massage the intervals into shape first. To pretend that the intervals are integers, we add 1 to the upper bound (making sure that the union of [1,3] and [4,9] is [1,9]). At the end, we undo this operation, and turn the result back into a list of lists.

There's also a completely different approach, which clocks in at 73 bytes:

NumericalSort@#//.{x___,{a_,b_},{c_,d_},y___}/;b+1>=c:>{x,{a,b~Max~d},y}&

Here, after sorting the intervals, we just replace two consecutive intervals by their union whenever that would be a single interval, and repeat until there is no such operation left to be done.

Answer 8

05AB1E (legacy), 88 79 78 bytes

g≠i˜AKïDW<UZ>VIøεAXY‚Nè:}ïø{©˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàDYQiA}V®нßDXQiA}Y‚

Infinity is input as the lowercase alphabet ('abcdefghijklmnopqrstuvwxyz').

Try it online or verify all test cases.

Important note: If there was an actual Infinity and -Infinity, it would have been 43 42 bytes instead. So little over 50% around 30% is as work-around for the lack of Infinity..

{©Dg≠i˜¦2ôíÆ1›.œʒíεćsO_*}P}н€g®£εø©θàV®нßY‚

Try it online (with Infinity replaced with 9999999999 and -Infinity replaced with -9999999999).

Can definitely be golfed substantially. In the end it turned out very, very ugly full of workarounds. But for now I'm just glad it's working.

Explanation:

Dg≠i          # If the length of the implicit input is NOT 1:
              #   i.e. [[1,3]] → length 1 → 0 (falsey)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → length 8 → 1 (truthy)
    ˜         #  Take the input implicit again, and flatten it
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
     AK       #  Remove the alphabet
              #   i.e. [1,4,"a..z",-5,3,7,38,40,8,9,11,20,25,"a..z",15,23]
              #    → ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
       ï      #  Cast everything to an integer, because `K` turns them into strings..
              #   i.e. ['1','4','-5','3','7','38','40','8','9','11','20','25','15','23']
              #    → [1,4,-5,3,7,38,40,8,9,11,20,25,15,23]
        D     #  Duplicate it
         W<   #  Determine the min - 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → -5
           U  #  Pop and store it in variable `X`
         Z>   #  Determine the max + 1
              #   i.e. [1,4,-5,3,7,38,40,8,9,11,20,25,15,23] → 40
           V  #  Pop and store it in variable `Y`
Iø            #  Take the input again, and transpose/zip it (swapping rows and columns)
              #   i.e. [[1,4],["a..z",-5],[3,7],[38,40],[8,9],[11,20],[25,"a..z"],[15,23]]
              #    → [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
  ε       }   #  Map both to:
   A          #   Push the lowercase alphabet
    XY‚       #   Push variables `X` and `Y`, and pair them into a list
       Nè     #   Index into this list, based on the index of the mapping
         :    #   Replace every alphabet with this min-1 or max+1
              #   i.e. [[1,'a..z',3,38,8,11,25,15],[4,-5,7,40,9,20,'a..z',23]]
              #    → [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
ï             #  Cast everything to integers again, because `:` turns them into strings..
              #   i.e. [['1','-6','3','38','8','11','25','15'],['4','-5','7','40','9','20','41','23']]
              #    → [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
 ø            #  Now zip/transpose back again
              #   i.e. [[1,-6,3,38,8,11,25,15],[4,-5,7,40,9,20,41,23]]
              #    → [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
  {           #  Sort the pairs based on their lower range (the first number)
              #   i.e. [[1,4],[-6,-5],[3,7],[38,40],[8,9],[11,20],[25,41],[15,23]]
              #    → [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
   ©          #  Store it in the register (without popping)
˜             #  Flatten the list
              #   i.e. [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
 ¦            #  And remove the first item
              #   i.e. [-6,-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
  2ô          #  Then pair every two elements together
              #   i.e. [-5,1,4,3,7,8,9,11,20,15,23,25,41,38,40]
              #    → [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
    í         #  Reverse each pair
              #   i.e. [[-5,1],[4,3],[7,8],[9,11],[20,15],[23,25],[41,38],[40]]
              #    → [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
     Æ        #  Take the difference of each pair (by subtracting)
              #   i.e. [[1,-5],[3,4],[8,7],[11,9],[15,20],[25,23],[38,41],[40]]
              #    → [6,-1,1,2,-5,2,-3,40]
      1›      #  Determine for each if they're larger than 1
              #   i.e. [6,-1,1,2,-5,2,-3,40] → [1,0,0,1,0,1,0,1]
.œ            #  Create every possible partition of these values
              #   i.e. [1,0,0,1,0,1,0,1] → [[[1],[0],[0],[1],[0],[1],[0],[1]],
              #                             [[1],[0],[0],[1],[0],[1],[0,1]],
              #                             ...,
              #                             [[1,0,0,1,0,1,0],[1]],
              #                             [[1,0,0,1,0,1,0,1]]]
  ʒ         } #  Filter the partitions by:
   í          #   Reverse each inner partition
              #    i.e. [[1],[0,0,1],[0,1],[0,1]] → [[1],[1,0,0],[1,0],[1,0]]
    ε     }   #   Map each partition to:
     ć        #    Head extracted
              #     i.e. [1,0,0] → [0,0] and 1
              #     i.e. [1] → [] and 1
              #     i.e. [1,0,1] → [1,0] and 1
      s       #    Swap so the rest of the list is at the top of the stack again
       O      #    Take its sum
              #     i.e. [0,0] → 0
              #     i.e. [] → 0
              #     i.e. [1,0] → 1
        _     #    And check if it's exactly 0
              #     i.e. 0 → 1 (truthy)
              #     i.e. 1 → 0 (falsey)
         *    #    And multiply it with the extracted head
              #    (is only 1 when the partition has a single trailing 1 and everything else a 0)
              #     i.e. 1 and 1 → 1 (truthy)
              #     i.e. 1 and 0 → 0 (falsey)
           P  #   And check if all mapped partitions are 1
н             #  Take the head (there should only be one valid partition left)
              #   i.e. [[[1],[0,0,1],[0,1],[0,1]]] → [[1],[0,0,1],[0,1],[0,1]]
 €g           #  Take the length of each inner list
              #   i.e. [[1],[0,0,1],[0,1],[0,1]] → [1,3,2,2]
   ®          #  Push the sorted pairs we've saved in the register earlier
    £         #  Split the pairs into sizes equal to the partition-lengths
              #   i.e. [1,3,2,2] and [[-6,-5],[1,4],[3,7],[8,9],[11,20],[15,23],[25,41],[38,40]]
              #    → [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
ε             #  Map each list of pairs to:
 ø            #   Zip/transpose (swapping rows and columns)
              #    i.e. [[1,4],[3,7],[8,9]] → [[1,3,8],[4,7,9]]
              #    i.e. [[25,41],[38,40]] → [[25,38],[41,40]]
  ©           #   Store it in the register
   θ          #   Take the last list (the ending ranges)
              #    i.e. [[25,38],[41,40]] → [41,40]
    à         #   And determine the max
              #    i.e. [41,40] → 41
     DYQi }   #   If this max is equal to variable `Y`
              #     i.e. 41 (`Y` = 41) → 1 (truthy)
         A    #    Replace it back to the lowercase alphabet
           V  #   Store this max in variable `Y`
  ®           #   Take the zipped list from the register again
   н          #   This time take the first list (the starting ranges)
              #    i.e. [[25,38],[41,40]] → [25,38]
    ß         #   And determine the min
              #    i.e. [25,38] → 25
     DXQi }   #   If this min is equal to variable `X`
              #     i.e. 25 (`X` = -6) → 0 (falsey)
         A    #    Replace it back to the lowercase alphabet
           Y‚ #   And pair it up with variable `Y` (the max) to complete the mapping
              #    i.e. 25 and 'a..z' → [25,'a..z']
              #  Implicitly close the mapping (and output the result)
              #   i.e. [[[-6,-5]],[[1,4],[3,7],[8,9]],[[11,20],[15,23]],[[25,41],[38,40]]]
              #    → [['a..z',-5],[1,9],[11,23],[25,'a..z']]
              # Implicit else (only one pair in the input):
              #  Output the (implicit) input as is
              #   i.e. [[1,3]]

Answer 9

C (clang), 346 342 bytes

Compiler flags -DP=printf("(%d,%d)\n",-DB=a[i+1], and -DA=a[i]

typedef struct{int a,b;}t;s(t**x,t**y){if((*x)->a>(*y)->a)return 1;else if((*x)->a<(*y)->a)return -1;}i;f(t**a){for(i=0;A;)i++;qsort(a,i,sizeof(t*),s);for(i=0;B;i++){if(B->a<=A->b+1){A->b=B->b;if(B->a<A->a)A->a=B->a;else B->a=A->a;}}for(i=0;A;i++){if(!B)break;if(A->a!=B->a)P,A->a,A->b);}P,A->a,A->b);}

Try it online!