'''
keys: make use of the fact the the intervals are already sorted
Solutions:
Similar:
T: 
S: 
'''
from typing import List



class Solution:
    
    # recommend this version
    # T: O(N), N as number of intervals
    # S: O(N)
    def insert1(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        newStart, newEnd = newInterval[0], newInterval[1]
        i = 0
        # add all the intervals ending before newInterval starts
        while i < len(intervals) and newStart > intervals[i][1]:
            res.append(intervals[i])
            i += 1
        # merge all overlapping intervals to one considering newInterval
        while i < len(intervals) and newEnd >= intervals[i][0]:
            newStart = min(newStart, intervals[i][0])
            newEnd = max(newEnd, intervals[i][1])
            i += 1
        res.append([newStart, newEnd]) # add the union of intervals we got
        while i < len(intervals): # add all the rest
            res.append(intervals[i])
            i += 1
        return res
            
            
    
    # greedy: standard solution with O(nlogn) time complexity
    # T: O(n) since already sorted; S: O(n)
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # init data
        new_start, new_end = newInterval
        idx, n = 0, len(intervals)
        output = []
        
        # add all intervals starting before newInterval
        while idx < n and new_start > intervals[idx][0]:
            output.append(intervals[idx])
            idx += 1
            
        # add newInterval
        # if there is no overlap, just add the interval
        if not output or output[-1][1] < new_start:
            output.append(newInterval)
        # if there is an overlap, merge with the last interval
        else:
            output[-1][1] = max(output[-1][1], new_end)
        
        # add next intervals, merge with newInterval if needed
        while idx < n:
            interval = intervals[idx]
            start, end = interval
            idx += 1
            # if there is no overlap, just add an interval
            if output[-1][1] < start:
                output.append(interval)
            # if there is an overlap, merge with the last interval
            else:
                output[-1][1] = max(output[-1][1], end)
        return output
    
    
    