[Leetcode] – Insert Interval Solution

7

In this problem, we are given a list of non-overlapping intervals sorted by their start times, along with a new interval. The goal is to insert the new interval into the list while ensuring the intervals remain non-overlapping and sorted. If necessary, overlapping intervals should be merged.

The tricky part of this problem lies in handling overlapping intervals efficiently while maintaining the sorted order. We also need to consider edge cases, such as when the new interval does not overlap with any existing intervals or when it encompasses multiple intervals.

Input: intervals =[[1, 3], [6, 9]]
newInterval = [2, 5]
Output: [[1, 5], [6, 9]]
Explanation: The new interval overlaps with [1, 3]. Merging them gives [1, 5].

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 14]]
newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 14]]
Explanation: The new interval overlaps with [3, 5], [6, 7], and [8, 10]. Merging them gives [3, 10].

Brute Force Approach

The brute force approach involves iterating through the intervals and manually merging all overlapping intervals, including the new interval.

Steps:

1. Append the new interval to the list of intervals.
2. Sort the intervals by their start times.
3. Initialize an empty list, merged, to store the merged intervals.
4. Iterate through the sorted intervals:
   • If the current interval overlaps with the last interval in merged, merge them by updating the end time of the last interval.
   • Otherwise, add the current interval to merged.
5. Return the merged list as the final result.

Time Complexity: Sorting the intervals takes O(n * log\ n), and merging requires a single pass through the intervals, taking O(n). The overall time complexity is O(n * log\ n).

While the brute force solution is straightforward, sorting the intervals adds unnecessary overhead, especially when the input is already sorted. Let’s explore a more efficient approach.

Efficient Solution

To solve this problem efficiently, we can iterate through the intervals and handle three cases:

1. Add intervals that end before the new interval starts.
2. Merge overlapping intervals with the new interval.
3. Add intervals that start after the new interval ends.

This approach ensures we only make a single pass through the intervals.

Steps:

1. Initialize an empty list, result, to store the final intervals.
2. Iterate through the input intervals while handling the following:
   • If the current interval ends before the new interval starts, add it to result.
   • If the current interval overlaps with the new interval, update the start and end times of the new interval by merging them.
   • If the current interval starts after the new interval ends, add the new interval to result and all remaining intervals.
3. If the new interval hasn’t been added by the end of the loop, append it to result.
4. Return result as the final list of intervals.

Code:

  int[][] insert(int[][] intervals, int[] newInterval) {
    int[][] result = new int[intervals.length + 1][2];
    int i = 0, j = 0;

    // Add all intervals that end before the new interval starts
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
      result[j++] = intervals[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]);
    }

    result[j++] = newInterval;

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

    return java.util.Arrays.copyOf(result, j);
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

Video Explanation: