Leetcode September Day12

Problem Statement - *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*

Example -
"""
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
"""
My initial approach - insert the newInterval at a position such that the intervals array remain sorted by start of each interval.
After I have inserted the newInterval, I can merge all the intervals wherever possible.
Solution

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        intervals.append(newInterval)
        intervals = sorted(intervals, key = lambda x : x[0])
        # now merge the intervals
        i = 1
        while i < len(intervals):
            p_i = intervals[i-1]
            c_i = intervals[i]
            if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
                intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
                del intervals[i]
            else:
                i += 1
        return intervals

TC - O(nlogn + n^2) because of sorting and deletion.

How can we optimise it ??

We can use binary search to determine the index.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [newInterval]
        intervals.append(newInterval)
        intervals = sorted(intervals, key = lambda x : x[0])
        lo = 0
        hi = len(intervals) - 1
        idx = 0
        while lo < hi:
            mid = (lo + hi)//2
            if intervals[mid][0] <= newInterval[0]:
                idx = max(idx, mid)
                lo = mid + 1
            else:
                hi = mid - 1
        intervals.insert(idx + 1, newInterval)
        # now merge the intervals
        i = 1
        while i < len(intervals):
            p_i = intervals[i-1]
            c_i = intervals[i]
            if p_i[0] <= c_i[0] and c_i[0] <= p_i[-1]:
                intervals[i-1] = [p_i[0], max(c_i[-1], p_i[-1])]
                del intervals[i]
            else:
                i += 1
        return intervals