Insert Intveral

Merge Intervals

Problem

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

For example:

Input: intervals = [[1,3],[6,9]], 
newInterval = [2,5]

Output: [[1,5],[6,9]]

Input: 
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], 
newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8]
overlaps with [3,5],[6,7],[8,10].

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Thought Process

Solution

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i, start, end = 0,0,1
        
        #finding interval where interval[i].end >= newInterval[start]
        while i < len(intervals) and newInterval[start] > intervals[i][end]:
            res.append(intervals[i])
            i+=1
            
        #if interval[start] is less than newInterval[end] this means we can merge
        #We borrowing "intervals[i][start] <= newInterval[end]" from Merge Interval
        while i < len(intervals) and intervals[i][start] <= newInterval[end]:
            newInterval[start] = min(newInterval[start], intervals[i][start])
            newInterval[end] = max(newInterval[end], intervals[i][end])
            i+=1
        
        res.append(newInterval)
        
        while i < len(intervals): #place the rest of the intervals
            res.append(intervals[i])
            i+=1
        return res
        
#Time: O(n)
#Space: O(n)