Python Solution (Beat Over 93%)


  • 0
    J

    when newInterval.start <= intervals[i].end, there is a chance for element i to be overlapped, so add its index into a list. if newInterval.end < intervals[i].start, the element i will not be overlapped, so delete it from the list.

     def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            length = len(intervals)
            start, end = newInterval.start, newInterval.end
            overlap_idx = []
            i=0
            idx = 0
            if(length == 0):
                return [newInterval]
            while(i < length):
                if(start <= intervals[i].start):
                    break
                i += 1
            idx = max(0, i - 1)
            while(idx < length):
                
                if(start <= intervals[idx].end):
                    overlap_idx.append(idx)
                if(end < intervals[idx].start):
                    overlap_idx.remove(idx)
                    break
                idx += 1
            if(not overlap_idx):
                intervals.insert(i, newInterval)
                return intervals
            new = Interval(s = min(intervals[overlap_idx[0]].start, start), e = max(intervals[overlap_idx[-1]].end, end))  
            return intervals[:overlap_idx[0]] + [new] + intervals[overlap_idx[-1] + 1:]
            
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.