# Range interval insert which should split into unique ranges

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.

• Should the intervals in the old list be preserved and not concatenated together in the new list? Jan 8 '19 at 21:59
• Intervals in the old list should remain as is, the new inserted ranges should have same end value as the next start value [[1, 2], [2, 5]] Jan 8 '19 at 22:02
• I'm a bit surprised nobody has mentioned The Sandbox where you can get feedback on your challenges before posting to main. I think this is a good challenge, as soon as I can figure out what it's asking. Jan 10 '19 at 21:36
• Would it be possible to have a different explanation of the task? I don't understand what "Given a range and a list thereof" even means. A list of a range? What? :) Jan 16 '19 at 3:47

# 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

• Nice answer, which is actually pretty similar to mine, so obvious +1 from me. I've also added the test cases [[1,1]], [3,3] and [[2,2]], [1,3] now (and fixed the code for [[1,1]], [3,3] since it was previously failing). Jan 11 '19 at 11:11
• Nice answer, working with ranges can be tricky in Japt. I originally thought there was no way to improve on £[XÎXÌ]Ã, but it turns out you can do ®gJõ0Ã to save 2 bytes :-) Jan 15 '19 at 21:06
• @ETHproductions Nice find, I always forget the other overloads of g Jan 15 '19 at 21:09

# 05AB1E, 3433 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!

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)


# Python 2, 119118 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!