Insert Interval medium

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

Steps

1. Initialization: Create a result list to store the merged intervals.

2. Handling Intervals Before Overlap: Iterate through the input intervals. Add any interval that completely precedes the newInterval (its end is less than the newInterval's start) to the result list.

3. Handling Overlapping Intervals: Once we encounter an interval that overlaps with newInterval (its start is less than or equal to newInterval's end), we start merging. We update the newInterval to encompass all overlapping intervals. We continue iterating and merging until we reach an interval that does not overlap.

4. Adding the Merged Interval: After the merging phase, add the updated newInterval to the result list.

5. Handling Remaining Intervals: Add any remaining intervals from the input list (those that come after the overlap) to the result list.

Explanation

The core idea is to efficiently handle three cases: intervals before the overlap, intervals during the overlap, and intervals after the overlap. By keeping track of the merged interval's boundaries, we can smoothly merge overlapping intervals without resorting to complex nested loops.

Code

def insert(intervals, newInterval):
    """
    Inserts a new interval into a sorted list of non-overlapping intervals, merging if necessary.

    Args:
        intervals: A list of lists, where each inner list represents an interval [start, end].
        newInterval: A list representing the new interval to be inserted [start, end].

    Returns:
        A list of lists representing the merged intervals.
    """
    result = []
    i = 0
    # Add intervals before overlap
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    # Add the merged interval
    result.append(newInterval)

    # Add remaining intervals
    while i < len(intervals):
        result.append(intervals[i])
        i += 1

    return result

Complexity

• Time Complexity: O(N), where N is the number of intervals. We iterate through the list of intervals at most once.
• Space Complexity: O(N) in the worst case, as the result list could contain all the original intervals plus the new one. In the best case, space complexity is O(1).