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.
Advertisement
Answer
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]]