Interval insert by exclusively adding an interval to a list of intervals

MichiganMagician 0
Viewed 42

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.

intersection algorithm python
1 Answers

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]]

Scaro9740
Related