Merge a new interval into given array of intervals

Question

This is Merge Intervals problem from www.interviewbit.com

Problem : Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9] insert and merge [2,5] :
result [1,5],[6,9].

Example 2:

Given intervals [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9]
result in [1,2],[3,10],[12,16]

My Approach:

def insert( intervals, new_interval):
    """returns list of intervals after merging"""
    count = 0
    status = False
    final_interval = []
    k = len(intervals)
    new_interval =  (min(new_interval),max(new_interval))
    for i in range(k):

        ## if new interval lesser than given interval
        if min(new_interval) < min(intervals[i]) and max(new_interval) < min(intervals[i]):
            status = False
            break 

        ## if new interval falls under given interval
        elif min(new_interval) >= min(intervals[i]) and max(new_interval)<= max(intervals[i]):
            status = True
            break 

        ## if given interval falls under new interval    
        elif min(new_interval) <= min(intervals[i]) and max(new_interval)>= max(intervals[i]):
            intervals.remove(intervals[i])
            status = True
            intervals.insert(i, new_interval)


        ## part of new interval overlaps with left part of given interval
        elif min(new_interval) <= max(intervals[i]) and min(new_interval) >= min(intervals[i]):
            intervals[i][1]  = max(new_interval)
            new_interval = intervals[i] 
            status = True

        ## part of new interval overlaps with right part of given interval
        elif max(new_interval) > min(intervals[i])and max(new_interval) <= max(intervals[i]):

            new_interval[1]  = max(intervals[i])
            intervals.remove(intervals[i])
            status = True
            intervals.insert(i, new_interval)
        count+= 1               
    if not status:
        intervals.insert(count,new_interval)

    for elem in intervals:
        if elem not in final_interval:
            final_interval.append(elem)

    return final_interval 

Test Cases:

print insert([[1,2],[3,6]],[8,10])
print insert([[3,5],[7,9]],[1,10])
print insert([[3,6],[8,10]],[1,2])
print insert([[1,2],[8,10]],[3,6])
print insert([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,9])
print insert([[1,3],[6,9]],[2,5])

How can this problem be solved in a better way?

Answer 1

Avoid indexing repetitively. You know that you'll want intervals[i] frequently within the loop, so index it once... or better yet, loop on it efficiently in the first place:

for i, (low, high) in enumerate(intervals):
    if new_interval[0] < low and new_interval[1] < low:
        # ...

Along the same lines, you frequently want the know the min and max of the new interval; you already compute these values, why keep it as a tuple that has to be indexed again and again?

new_low, new_high = min(new_interval), max(new_interval)
# ...
for i, (low, high) in enumerate(intervals):
    if new_low < low and new_high < low:
        # ...

---

Use my_list.pop(i) instead of my_list.remove(my_list[i]). The first requires Python to iterate through the list element by element, check for equality against my_list[i], and remove the first equal element it finds; the second tells it exactly what part of the list you want gone much more efficiently, since you already know the location i.

Better yet, use an approach that doesn't modify intervals at all (no popping or inserting). It's entirely possible to solve this problem by only appending new outputs to final_interval with no other list mutations. That's particularly important if you're iterating on intervals, in which case mutating it within the for loop will break your code.

---

Your final loop is O(N^2), which is not necessary for this problem:

for elem in intervals:  # O(n)
    if elem not in final_interval:  # O(n)
        final_interval.append(elem)

Since you know that the values in intervals are sorted already, I would instead suggest an approach that stops the first loop after you've output new_interval and all intervals it overlaps with, then the second loop just pumps out the remaining items from where the first loop left off.

---

And now to actually answer your specific error: you've defined your function to work on a list of lists (or tuples, whatever), and return the same; the actual problem hosted on the site provides a list of Interval objects and expects a list of Interval objects back. This is easy to support:

def insert(self, intervals, new_interval):
    intervals = [(v.start, v.end) for v in intervals]
    new_interval = (new_interval.start, new_interval.end)
    new_low, new_high = min(*new_interval), max(*new_interval)
    # ...
    return [Interval(l, h) for l, h in final_interval]