📎57. Insert Interval

Medium | Grind 75 | August 29th Monday, 2022

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Constraints:

• 0 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= starti <= endi <= 10^5

• intervals is sorted by starti in ascending order.

• newInterval.length == 2

• 0 <= start <= end <= 10^5

Example 1

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

Example 2

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].

SOLUTION

We will first add the new interval to the intervals list and sort the list. NOTE: it is important to sort the interval list because our merge algorithm assume the list is sorted. Once we have sorted the interval list, we will now perform the merging of the intervals.

1. iterate over every element in the intervals list.

2. Take the first element in the interval list.

   1. store the intervals of the current element as start and end.

3. In order to find intervals that overlap, check if the start value is equal to the start of the next element or the current end value is greater than the start value of next element. If yes:

   1. set the start as the minimum of current start and the next element start.

   2. set the end as the maxmimum of current end and the end value of the next element.

   3. look at the next next element and compare to start and end value.

4. Append the start and end value in your new merged interval list.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        """ IDEA: add the new interval in the intervals list and then merge the interval list """
        
        # add the new interval and sort interval list.
        intervals.append(newInterval)
        intervals.sort()
        
        merged_interval = []
        i = 0
        while i < len(intervals): 
            # initialize start and end as the current element's interval
            start, end = intervals[i][0], intervals[i][1]
            
            # given that there is more elements in the list left
            if i + 1 < len(intervals): 
                
                # merge: if start is same as the start of the next element or
                #        the end is bigger than the start of the next element. 
                while start == intervals[i+1][0] or end >= intervals[i+1][0]: 
                    
                        # start should be the minimum of the compared elements 
                        start = min(start, intervals[i+1][0])
                        
                        # end should be the max of the compared elements
                        end = max(end, intervals[i+1][1])
                        
                        # set next element as the current element
                        i += 1
                        
                        # we have run out of elements in the interval
                        if i+1 >= len(intervals):
                            break
                            
            i += 1
                        
            merged_interval.append([start, end])
            
        return merged_interval
                        
                         
                    

TIME AND SPACE COMPLEXITY

TIME: O(nlogn) where n is the length of the interval list. We get a runtime of O(nlogn) because of the sort that we perform after adding the new interval in the list. You could on average have a better runtime(O(n)) with a different solution but in the worst case, even that solution will be O(nlogn)

SPACE: O(n) our new merged intervals in the worst case will store n+1 elements.