2
\$\begingroup\$

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?

\$\endgroup\$
4
  • 2
    \$\begingroup\$ You're running Python 2. What version are they running? \$\endgroup\$
    – Mast
    May 17, 2018 at 19:34
  • \$\begingroup\$ @ Mast they are also using Python 2 \$\endgroup\$ May 18, 2018 at 0:49
  • \$\begingroup\$ does the code you have posted here, work on the website you coded it for? \$\endgroup\$
    – Malachi
    May 18, 2018 at 17:11
  • \$\begingroup\$ @Malachi yes the code posted here works on the website after i made changes in the type of received inputs and returned output,since this code was defined in a class which was subclass of another class interval. But here no need to change cause i want to optimise the function or the logic used, no class defined here . \$\endgroup\$ May 19, 2018 at 2:40

1 Answer 1

3
\$\begingroup\$

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]
\$\endgroup\$
1
  • \$\begingroup\$ @scenerd thanks for review and pointing out the mistake \$\endgroup\$ May 21, 2018 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.