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 were initially sorted according to their start times.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Explanation: Because the new interval [2,5] overlaps with [1,3], they merged into one new interval [1,5].

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], they merged into one new interval [3,10].

Steps

1. Handle empty intervals: If the input intervals array is empty, simply return an array containing only the newInterval.

2. Initialize results: Create an empty array result to store the merged intervals.

3. Iterate and merge: Iterate through the intervals array. For each interval:

   • If the current interval's end is less than the newInterval's start, it doesn't overlap, so add it to the result array.
   • If the current interval's start is less than the newInterval's end, there's an overlap. Update the newInterval to encompass the overlap (by updating its start and end).
   • Continue iterating until we reach an interval that doesn't overlap with newInterval (or until the end of the intervals array).

4. Add the new interval: After the loop, add the potentially updated newInterval to the result array.

5. Add remaining intervals: Add any remaining intervals from the input array to the result array.

Explanation

The algorithm efficiently handles overlapping intervals by merging them iteratively. By tracking the newInterval and comparing it with each existing interval, we dynamically adjust its boundaries to incorporate overlaps. The use of separate arrays for results and input ensures that the original input remains unchanged, while the results are systematically built through additions and merges.

Code

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];
    let i = 0;

    // Add intervals before overlap
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push(newInterval);

    // Add remaining intervals
    while (i < intervals.length) {
        result.push(intervals[i]);
        i++;
    }

    return result;
}

Complexity

• Time Complexity: O(N), where N is the number of intervals. We iterate through the intervals array at most twice.
• Space Complexity: O(N) in the worst case, if we have to store all the intervals in the result array. In the best case (no overlaps), space complexity is O(1) if the input array can be modified directly, otherwise O(N) to create a new result array.