insert-interval.py

# Leetcode 57. Insert Interval
#
# Link: https://leetcode.com/problems/insert-interval/
# Difficulty: Medium

# Solution using DP.
# Complexity:
#   O(N) time | where N represent the number of intervals
#   O(1) space
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

        result = []

        for i in range(len(intervals)):

            if newInterval[1] < intervals[i][0]:

                result.append(newInterval)
                return result + intervals[i:]

            elif newInterval[0] > intervals[i][1]:

                result.append(intervals[i])

            else:

                newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]

        result.append(newInterval)

        return result