algoadvance

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i.

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 start_i and intervals still does not have any overlapping intervals. Return intervals after the insertion.

Example:

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

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

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

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Clarifying Questions

  1. Input Constraints: Are there any constraints on the size of the intervals array or the values of start and end?
  2. Merge Logic: If the new interval’s start or end is already covered by an existing interval, can we assume it is part of the merging rule?
  3. Empty Input: Is it correct to return a single interval if the input intervals array is empty?
  4. Output Format: Can we assume the output should be the intervals array with the new interval inserted in the appropriate place and merged if necessary?

Strategy

  1. Initialization: Create an empty list to store the result.
  2. Iterate Through Intervals:
    • Add all intervals that end before the start of the new interval to the result.
    • While the current interval overlaps with the new interval, merge them.
    • Add remaining intervals to the result.
  3. Edge Cases: Handle cases where intervals is empty or the new interval does not overlap with any current interval.
  4. Return the Result: The merged and sorted intervals.

Code

Here’s the implementation of the above strategy:

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)
    
    # Add intervals before the new interval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # Merge overlapping intervals with new interval
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    
    result.append(newInterval)
    
    # Add remaining intervals after new interval
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

Time Complexity

Try our interview co-pilot at AlgoAdvance.com