python O(n) solution, 78ms


  • 0
    class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            #init
            if not intervals:
                return [newInterval]
            if not newInterval:
                return intervals
            res = []
            pos = 0
            #traverse the list, merge if overlapping
            for inter in intervals:
                if inter.end < newInterval.start:
                    res.append(inter)
                    pos += 1
                elif inter.start > newInterval.end:
                    res.append(inter)
                else:
                    newInterval.start = min(inter.start, newInterval.start)
                    newInterval.end = max(inter.end, newInterval.end)
            res.insert(pos, newInterval)
            return res
    

Log in to reply
 

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