'''
Problem Statement 
Given a list of non-overlapping intervals sorted by their start time, insert a given interval at the correct position and merge all necessary intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,6]
Output: [[1,3], [4,7], [8,12]]
Explanation: After insertion, since [4,6] overlaps with [5,7], we merged them into one [4,7].

Example 2:

Input: Intervals=[[1,3], [5,7], [8,12]], New Interval=[4,10]
Output: [[1,3], [4,12]]
Explanation: After insertion, since [4,10] overlaps with [5,7] & [8,12], we merged them into [4,12].

Example 3:

Input: Intervals=[[2,3],[5,7]], New Interval=[1,4]
Output: [[1,4], [5,7]]
Explanation: After insertion, since [1,4] overlaps with [2,3], we merged them into one [1,4].
'''


#mycode
def insert(self, intervals, newInterval):
    """
    :type intervals: List[List[int]]
    :type newInterval: List[int]
    :rtype: List[List[int]]
    """
    idx = self.findInsertPosition(intervals, newInterval)
    intervals = self.insertInterval(intervals, newInterval, idx)
    return self.mergeIntervals(intervals)
    
def findInsertPosition(self, intervals, new_interval):
    start_new = new_interval[0]
    for idx, (start, _) in enumerate(intervals):
        if start_new <= start:
            return idx
    return -1

def insertInterval(self, intervals, new_interval, idx):
    if idx == -1:
        intervals.append(new_interval)
    else:
        intervals.insert(idx, new_interval)
    return intervals

def mergeIntervals(self, intervals):
    merged = []
    for i, (start, end) in enumerate(intervals):
        if not merged or merged[-1][1] < start:
            merged.append(intervals[i])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged


def main():
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 6])))
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 10])))
  print("Intervals after inserting the new interval: " + str(insert([[2, 3], [5, 7]], [1, 4])))


main()



#answer
def insert(intervals, new_interval):
  merged = []
  i, start, end = 0, 0, 1

  # skip (and add to output) all intervals that come before the 'new_interval'
  while i < len(intervals) and intervals[i][end] < new_interval[start]:
    merged.append(intervals[i])
    i += 1

  # merge all intervals that overlap with 'new_interval'
  while i < len(intervals) and intervals[i][start] <= new_interval[end]:
    new_interval[start] = min(intervals[i][start], new_interval[start])
    new_interval[end] = max(intervals[i][end], new_interval[end])
    i += 1

  # insert the new_interval
  merged.append(new_interval)

  # add all the remaining intervals to the output
  while i < len(intervals):
    merged.append(intervals[i])
    i += 1
  return merged


def main():
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 6])))
  print("Intervals after inserting the new interval: " + str(insert([[1, 3], [5, 7], [8, 12]], [4, 10])))
  print("Intervals after inserting the new interval: " + str(insert([[2, 3], [5, 7]], [1, 4])))


main()


'''
Time complexity 
As we are iterating through all the intervals only once, the time complexity of the above algorithm is O(N)O, 
where ‘N’ is the total number of intervals.

Space complexity 
The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals.
'''
