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]] Explanation: Because the new interval [2,5] overlaps with [1,3], we merged them into [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], we merged them into [3,10].

Steps

1. Handle Empty Intervals: If the input intervals is empty, simply return a list containing the newInterval.

2. Initialization: Create a list result to store the merged intervals. Initialize an index i to 0 to iterate through the existing intervals.

3. Iteration and Merging: Iterate through the intervals:

   • If the current interval's end time is less than the newInterval's start time, it doesn't overlap. Add it to the result list.
   • If the current interval's start time is less than or equal to the newInterval's end time, it overlaps (or touches) the newInterval. Update the newInterval's start and end times to encompass the overlap. Continue iterating, updating newInterval.
   • Once the loop finishes, add the merged newInterval to the result list.

4. Append Remaining Intervals: Add any remaining intervals from intervals (those after the overlap) to the result list.

Explanation

The algorithm efficiently handles overlapping intervals by iteratively merging them into the newInterval. The key idea is to track the overall start and end times of the merged intervals as we iterate through the list. We only add intervals to the result list that do not overlap with the newInterval. Once the iteration is complete and the merged newInterval has been formed, we append any remaining intervals from the original input.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new List<int[]>();
        int i = 0;

        // Add intervals before the overlap
        while (i < intervals.Length && intervals[i][1] < newInterval[0]) {
            result.Add(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.Add(newInterval);

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

        return result.ToArray();
    }
}

Complexity

• Time Complexity: O(n), where n is the number of intervals. We iterate through the intervals at most twice.
• Space Complexity: O(n) in the worst case, to store the result list. If there are no overlaps, the space complexity could be O(1) if the result were to be written over the existing input array. However, the typical solution requires extra space as shown above.