Merge a new interval into given array of intervals
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] &lt; low and new_interval[1] &lt; 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 &lt; low and new_high &lt; 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]