This is similar to this problem: https://leetcode.com/problems/insert-interval/
However, what I need is a bit different. I need to lower the smallest interval by 1 if to compare with the one I want to add and increase the next closest interval by one to with the one I want to add if there are intersections.
Say I have:
intervals: [0, 3],[4, 4],[5, 5] and I want to insert [3, 3], the result should be [[0, 2], [3, 3], [4, 4], [5,5]]
If I have intervals: [0, 3],[4, 4],[5, 5] and I want to insert [3, 4], the result should be [[0, 2], [3, 4], [5,5]]
If I have intervals: [0, 3],[4, 8],[9, 10] and I want to insert [5, 7], the result should be [[0, 3], [4, 4], [5, 7], [8, 8] [9, 10]]
Is there any efficient way to do it?
One important thing is that the interval I want to insert will always be between 0 and the last number of the current interval list. In the above examples, it would be between 0 and 5; 0 and 5; 0 and 10
This is my code which was unsuccessful:
test_case_1_grouped = [[0, 3], [4, 4], [5, 5]]
test_case_1_cargo = [3, 4]
expected = [[0, 2], [3, 4], [5, 5]]
test_case_2_grouped = [[0, 3], [4, 4], [5, 5]]
test_case_2_cargo = [3, 3]
expected = [[0, 2], [3, 3], [4, 4], [5, 5]]
test_case_3_grouped = [[0, 3], [4, 8], [9, 10]]
test_case_3_cargo = [5, 7]
expected = [[0, 3], [4, 4], [5, 7], [8, 8], [9, 10]]
test_case_4_grouped = [[0, 3], [4, 8], [9, 10]]
test_case_4_cargo = [4, 7]
expected = [[0, 3], [4, 7], [8, 8], [9, 10]]
test_case_5_grouped = [[0, 3], [4, 8], [9, 10]]
test_case_5_cargo = [2, 9]
expected =[[0, 1], [2, 9], [10, 10]]
test_case_6_grouped = [[0, 3], [4, 8], [9, 10]]
test_case_6_cargo = [0, 10]
expected = [[0, 10]]
def insert(interval_list, interval_insert):
inserted = False
result = []
first_number = interval_insert[0]
second_number = interval_insert[1]
flat_list = [item for sublist in interval_list for item in sublist]
if first_number in flat_list:
biggest_smaller_number_or_first_number = first_number
else:
f = filter(lambda x: x < first_number, flat_list)
biggest_smaller_number_or_first_number = max(f)
if second_number in flat_list:
smallest_bigger_number_or_second_number = second_number
else:
f = filter(lambda x: x > second_number, flat_list)
smallest_bigger_number_or_second_number = min(f)
if first_number == biggest_smaller_number_or_first_number and smallest_bigger_number_or_second_number == second_number:
for interval in interval_list:
if first_number in interval:
result.append([interval[0], first_number - 1])
result.append(interval_insert)
inserted = True
continue
if second_number in interval and interval == [second_number, second_number] and inserted:
continue
else:
result.append(interval)
elif first_number == biggest_smaller_number_or_first_number and smallest_bigger_number_or_second_number != second_number:
for interval in interval_list:
if first_number in interval:
result.append(interval_insert)
result.append([second_number + 1, smallest_bigger_number_or_second_number])
continue
else:
result.append(interval)
else:
for interval in interval_list:
if biggest_smaller_number_or_first_number in interval and smallest_bigger_number_or_second_number in interval:
result.append([biggest_smaller_number_or_first_number, first_number - 1])
result.append(interval_insert)
result.append([second_number + 1, smallest_bigger_number_or_second_number])
continue
elif biggest_smaller_number_or_first_number in interval and smallest_bigger_number_or_second_number not in interval:
result.append([biggest_smaller_number_or_first_number, first_number - 1])
result.append(interval_insert)
continue
elif biggest_smaller_number_or_first_number not in interval and smallest_bigger_number_or_second_number in interval:
result.append([smallest_bigger_number_or_second_number + 1, interval[1]])
continue
elif interval[0] > second_number or interval[1] < first_number:
result.append(interval)
return result
While it passes test cases 1-5, I always find a test case which does not pass meaning that my solution is buggy.
This code works but it is not optimized. I believe the use of operations on sets leads to efficient computing thow:
#split the union of two intervals into two distinct intervals
def split(int_set):
minimum = min(int_set)
maximum = max(int_set)
diff = set(range(minimum, maximum+1)) - int_set
if diff == set():
return [[minimum, maximum]]
else:
return [[minimum, min(diff)-1], [max(diff)+1, maximum]]
Example : split(set([1,2,3,4,5,7])): [[1, 5], [7, 7]]
#merge overlapping intervals
def merge(intervals):
new_intervals = []
intervals.append([intervals[-1][1], intervals[-1][1]])
i = 0
while i < len(intervals) - 1:
if intervals[i][1] == intervals[i+1][0]:
new_intervals.append([intervals[i][0], intervals[i+1][1]])
i += 2
else:
new_intervals.append([intervals[i][0], intervals[i][1]])
i += 1
return new_intervals
Example: merge([[0, 3], [4, 4], [5, 7], [8, 8], [8, 10]]): [[0, 3], [4, 4], [5, 7], [8, 10]]
#main fucntion insert()
def insert(intervals, NewInterval):
new_intervals = []
index = 0
for interval in intervals:
diff = set(range(interval[0], interval[1]+1)) - set(range(NewInterval[0], NewInterval[1]+1))
if len(diff) != 0:
diff = split(diff)
new_intervals += diff
if interval[0] < NewInterval[0]:
index += 1
new_intervals.insert(index, NewInterval)
return merge(new_intervals)
Example: insert([[0, 3],[4, 8],[5, 10]], [5,7]): [[0, 3], [4, 4], [5, 7], [8, 10]]