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
Time Limit exceeded for O(n) solution! what do they want? O(1)? Can anyone help me make my code faster?
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.