Python solution with detailed explanation


  • 0
    G

    Solution

    Insert Interval https://leetcode.com/problems/insert-interval/

    Algorithm

    class Solution(object):
        def merge(self, intervals):
            result = [intervals[0]]
            for i in range(1, len(intervals)):
                i1, i2 = result[-1], intervals[i]
                if i2.start > i1.end:
                    result.append(i2)
                elif i2.end >= i1.end:
                    i1.end = i2.end
            return result
    
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            result = []
            l1, l2 = intervals, [newInterval]
            i, j = 0, 0
            while i < len(l1) or j < len(l2):
                if i == len(l1):
                    result.append(l2[j])
                    j += 1
                elif j == len(l2):
                    result.append(l1[i])
                    i += 1
                elif l1[i].start <= l2[j].start:
                    result.append(l1[i])
                    i += 1
                else:
                    result.append(l2[j])
                    j += 1
            return self.merge(result)
    

Log in to reply
 

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