Insert Interval - Leetcode Solution

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

Approach:

The given problem can be efficiently solved using two pointers. First, we will iterate over the intervals, and we will stop as soon we find the last interval that starts before our new interval. Using another pointer, we will go over the remaining intervals. In each iteration, we will check whether the current interval ends before the start of our new interval or whether our new interval ends before the start of the current interval. In these two cases, we do not need to merge intervals. Otherwise, there is an overlap between the current interval and our new interval. We will create a new interval that represents the merged intervals, add it to our output, and continue iterating over the remaining intervals.

Algorithm:

1. Initialize index variable to point at 0-th position of the interval list
2. Iterate over the interval list as long as we do not reach the end of the list or the start of a new interval.
3. If the end of the current interval is less than the start of the new interval, increase the index variable to move to the next interval.
4. If the start of the current interval is greater than the end of the new interval, insert the new interval starting from the current index.
5. If there is an overlap between the current interval and the new interval, create a new merged interval.
6. Add remaining intervals to the merged interval as long as there is an overlap.
7. If there is no overlap with remaining intervals return the result.

Time Complexity:

The time complexity of the given algorithm is O(N), where N is the number of intervals in the input.

Space Complexity:

The space complexity of the given algorithm is O(N), where N is the number of intervals in the input.

Solution:

Here is the Python implementation of the above approach:

class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

    i, n = 0, len(intervals)
    result = []
    
    # insert intervals before the new interval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
        
    # merge overlapping intervals
    merged = newInterval
    while i < n and intervals[i][0] <= merged[1]:
        merged = [min(merged[0], intervals[i][0]), max(merged[1], intervals[i][1])]
        i += 1
    result.append(merged)
    
    # add the rest of the intervals
    while i < n:
        result.append(intervals[i])
        i += 1
        
    return result
    

The above solution is also available on my LeetCode account:

https://leetcode.com/submissions/detail/450431475/

1