Range interval insert which should split into unique ranges

Question

Given a range and a list thereof, while keeping the existing intervals in the list unchanged, split the additional range into sub-intervals and add them to the list, such that all the ranges in the final list are disjoint and contain all numbers present in the input ranges.

The goal is to create an insertInterval(intervals, newInterval) function which returns a new interval list if there are any changes.

Pre-condition: Interval range is sorted smallest to larger [[0, 1], [3, 5]].

Examples: Input and output:

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [12,27]),
  [[1,5],[10,15],[15,20],[20,25],[25, 27]]
);

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [-3,0]),
  [[-3,0],[1,5],[10,15],[20,25]]
);

assert.deepEqual(
  insertIntervalSec([[1,5],[10,15],[20,25]], [-3,3]),
  [[-3,1],[1,5],[10,15],[20,25]]
);

assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [15,15]),
  [[0,5],[10,15],[20,25]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [20,21]),
  [[0,5],[10,15],[20,25]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [26,27]),
  [[0,5],[10,15],[20,25],[26, 27]]
);
assert.deepEqual(
  insertIntervalSec([[0,5],[10,15],[20,25]], [25,27]),
  [[0,5],[10,15],[20,25],[25,27]]
);
assert.deepEqual(insertIntervalSec([], [25,27]), [[25,27]]);
assert.deepEqual(insertIntervalSec([[1,1]], [1,1]), [[1,1]]);
assert.deepEqual(insertIntervalSec([[1,1]], [1,3]), [[1, 1], [1, 3]]);
assert.deepEqual(insertIntervalSec([[2,2]], [1,3]), [[1, 2], [2, 2], [2, 3]]);

All programming languages are welcome.

Answer 1

Japt, 44 bytes

rò
íU c ò@Vc øX ©X¥YÃke@V®ròÃc øXîgJõ0ÃcV n

Try it online!

Reworked it, at the cost of 1 byte. Now handles the [[2,2]],[1,3] test case properly.

Explanation:

rò                                           #Turn the second input into a range
íU c                                         #Duplicate each item in that range
     ò@      ©X¥YÃ                           #Split in the middle of the duplicates that:
       Vc øX                                 # Appear in the first input
                  k                          #Remove the segments where:
                   e@       øXÃ              # Every item in the segment is in...
                     V®ròÃc                  # A range from the first input
                               ®    Ã        #For the remaining segments:
                                gJõ0         # Get the first and last items
                                     cV      #Add those pairs to the first input
                                        n    #Sort the whole thing

Worked Example:

Input: [[2,2],[5,7]],[1,8]

Second input as a range: [1,2,3,4,5,6,7,8]

Duplicate each item: [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8]

Numbers that appear in the first input: [2,5,7]

After splitting: [[1,1,2],[2,3,3,4,4,5],[5,6,6,7],[7,8,8]]

Numbers within the first input's ranges: [2,5,6,7]

Segments using only those numbers:[[5,6,6,7]]

Remaining segments after those are removed: [[1,1,2],[2,3,3,4,4,5],[7,8,8]]

First and last item of each: [[1,2],[2,5],[7,8]]

Merge with the first input: [[1,2],[2,5],[7,8],[2,2],[5,7]]

Sort it: [[1,2],[2,2],[2,5],[5,7],[7,8]]

Which matches the actual output of the code

Answer 2

05AB1E, 34 33 30 bytes

ŸεI˜yåiðy)]˜#ʒI€Ÿ˜KgĀ}εнyθ‚}«ê

Created a port of @KamilDrakari's Japt answer, in order to fix the new test case [[2,2]], [1,3] (which golfed 4 bytes at the same time). So make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

Ÿ            # Get the ranged list of the first (implicit) input
             #  i.e. [1,8] → [1,2,3,4,5,6,7,8]
 ε           # Map each number `y` to:
  I˜yåi      #  If the second input flattened contains the current map-number:
             #    i.e. [[2,2],[5,7]] and `y`=2 → 1 (truthy)
       ðy    #   Push a space character, and value `y` again
         )   #   Wrap `y`, space, `y` into a list
 ]           # Close the if-statement and the map
             #  i.e. [1,2,3,4,5,6,7,8] and [[2,2],[5,7]]
             #   → [1,[2," ",2],3,4,[5," ",5],6,[7," ",7],8]
  ˜          # Flatten the list
             #  i.e. [1,[2," ",2],3,4,[5," ",5],6,[7," ",7],8]
             #   → [1,2," ",2,3,4,5," ",5,6,7," ",7,8]
   #         # Split the list on spaces
             #  i.e. [1,2," ",2,3,4,5," ",5,6,7," ",7,8] → [[1,2],[2,3,4,5],[5,6,7],[7,8]]
ʒ       }    # Filter this list of lists by:
 I€Ÿ         #  Push the second input, and create a range of each pair
             #   i.e. [[2,2],[5,7]] → [[2],[5,6,7]]
    ˜        #  Flatten this list of lists
             #   i.e. [[2],[5,6,7]] → [2,5,6,7]
     K       #  Remove these numbers from the current filter-list
             #   i.e. [2,3,4,5] and [2,5,6,7] → [3,4]
             #   i.e. [5,6,7] and [2,5,6,7] → []
      g      #  Take the length of this list
             #   i.e. [3,4] → 2
             #   i.e. [] → 0
       Ā     #  And truthify it (0 remains 0; everything else becomes 1)
             #   i.e. 2 → 1 (truthy)
             #   i.e. 0 → 0 (falsey)
             #  i.e. [[1,2],[2,3,4,5],[5,6,7],[7,8]] and [[2,2],[5,7]]
             #   → [[1,2],[2,3,4,5],[7,8]]
ε    }       # Map each inner list to:
 н           #  Take the first value
             #   i.e. [2,3,4,5] → 2
  yθ         #  And the last value
             #   i.e. [2,3,4,5] → 5
    ‚        #  And pair them together
             #   i.e. 2 and 5 → [2,5]
             #  i.e. [[1,2],[2,3,4,5],[7,8]] → [[1,2],[2,5],[7,8]]
«            # Merge this list of pairs with the second (implicit) input
             #  i.e. [[2,2],[5,7]] and [[1,2],[2,5],[7,8]]
             #   → [[2,2],[5,7],[1,2],[2,5],[7,8]]
 ê           # Sort the list of pairs, and remove any duplicated pairs at the same time
             #  i.e. [[2,2],[5,7],[1,2],[2,5],[7,8]]
             #   → [[1,2],[2,2],[2,5],[5,7],[7,8]]
             # (and output the result implicitly)

Answer 3

Python 2, 119 118 116 bytes

lambda l,A,B:sum([[[max(A,b),min(c[0],B)],c][max(A,b)>=min(c[0],B):]for(a,b),c in zip([[A,A]]+l,l+[[B,B]])],[])[:-1]

Try it online!

---

If I/O can be flat lists (of even length):

Python 2, 112 bytes

lambda l,A,B:sum([[a]+[max(A,a),min(B,b)]*(max(A,a)<min(B,b))+[b]for a,b in zip(*[iter([A]+l+[B])]*2)],[])[1:-1]

Try it online!

---

Python 3, 111 bytes

lambda l,A,B:sum([[a]+[max(A,a),min(B,b)]*(max(A,a)<min(B,b))+[b]for a,b in zip(*[iter([A,*l,B])]*2)],[])[1:-1]

Try it online!