O(n) Python solution


  • 13
    X
    class Solution:
        # @param intervals, a list of Intervals
        # @param newInterval, a Interval
        # @return a list of Interval
        def insert(self, intervals, newInterval):
            start = newInterval.start
            end = newInterval.end
            result = []
            i = 0
            while i < len(intervals):
                if start <= intervals[i].end:
                    if end < intervals[i].start:
                        break
                    start = min(start, intervals[i].start)
                    end = max(end, intervals[i].end)
                else:
                    result.append(intervals[i])
                i += 1
            result.append(Interval(start, end))
            result += intervals[i:]
            return result

  • 7
    V

    Great idea! I made a little modification to make it in-place.

    class Solution:
    	def insert(self, intervals, newInterval):
    		start = newInterval.start
    		end = newInterval.end
    		right = left = 0
    		while right < len(intervals):
    			if start <= intervals[right].end:
    				if end < intervals[right].start:
    					break
    				start = min(start, intervals[right].start)
    				end = max(end, intervals[right].end)
    			else:
    				left += 1
    			right += 1
    		return intervals[:left] + [Interval(start, end)] + intervals[right:]

  • 0
    N
    class Solution:
    
        def merge(self, intervals):
            intervals.sort(lambda a,b: a.end - b.end)
            intervals.sort(lambda a,b: a.start - b.start)
            i, n = 0, len(intervals)
            result = []
            while i < n:
                s = i
                j = i + 1
                maxEnd = intervals[i].end
                while j < n and maxEnd >= intervals[j].start:
                    maxEnd = max(maxEnd, intervals[j].end)
                    i += 1
                    j += 1
                result.append(Interval(intervals[s].start, maxEnd))
                i = j
            return result
    
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            intervals.append(newInterval)
            return self.merge(intervals)

Log in to reply
 

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