Time Limit exceeded for O(n) solution! what do they want? O(1)? Can anyone help me make my code faster?


#1
def merge(self, intervals):
    intervals.sort(key=lambda x :x.start)
    n=len(intervals)
    if n<2:
        return intervals
    c=0
    for i in range(0,n):
        
        if i<len(intervals)-1 and intervals[i].end>= intervals[i+1].start:
           
            temp=Interval(min(intervals[i].start, intervals[i+1].start), max(intervals[i].end,intervals[i+1].end))
            temp2=Interval(-1,-1)
            del intervals[i:i+2]
            intervals.append(temp)
            intervals.append(temp2)
            c=c+1
            intervals.sort(key=lambda x :x.start)    
    
    intervals.sort(key=lambda x :x.start)
    del intervals[0:c:]
    return intervals

#2

you are rearranging the list which is a costly operation. And sorting the rearranged list which again is costly. this is why your solution is not O(n).
jsut make a new list to store the merged intervals.
you could probably keep the merged interval in a variable and push it to list when next inerval is not in range.
Hope this helps.