Insert New Interval and Merge Overlapping Intervals

Insert and Merge Overlapping Intervals: A Comprehensive Guide

Quick Summary: To insert a new interval and merge overlapping intervals in a sorted array, you iterate through the list sequentially. First, add all intervals that occur before the new interval. Next, merge any intervals that overlap with the new interval by finding the minimum start time and maximum end time. Finally, add the remaining intervals. This approach guarantees an optimal O(n) time complexity and ensures the resulting array remains sorted and non-overlapping.

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 event and intervals is sorted in ascending order by start_i. He wants to add a new interval newInterval= [newStart, newEnd] where newStart and newEnd represent the start and end of this interval.

Need to 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 (merge overlapping intervals if necessary). This fundamental algorithm problem often appears in technical interviews and real-world scheduling applications.

Examples:

Input: intervals = [[1,3], [4,5], [6,7], [8,10]], newInterval = [5,6]
Output: [[1,3], [4,7], [8,10]]
Explanation: The newInterval [5,6] overlaps with [4,5] and [6,7].

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,9]
Output: [[1,2], [3,10], [12,16]]
Explanation: The new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Constraints:
1 ≤ intervals.size() ≤ 10⁵
0 ≤ start[i], end[i] ≤ 10⁹

This problem involves inserting a new interval into a sorted, non-overlapping set of intervals and ensuring the resulting intervals remain sorted and non-overlapping. It also requires merging overlapping intervals as necessary. Because the array is already sorted, we can avoid the typical O(n log n) sorting step and achieve an efficient O(n) solution.

Key Steps to Solve the Problem

Determine Where to Insert the New Interval:
- Traverse the original list of intervals and insert the new interval in its appropriate position based on its start value. We identify intervals that end before the new interval begins and safely push them into the result array.
Merge Overlapping Intervals:
- After inserting the new interval, traverse the list of intervals and merge any overlapping intervals to ensure the intervals are non-overlapping. Overlap happens when the current interval's start time is less than or equal to the new interval's end time.
Preserve Sorting:
- Since the given list is already sorted and we insert the new interval at the correct position, the list remains sorted. Lastly, we append the remaining intervals that start after the new interval ends.

Efficient Algorithm Implementation

If there is an overlap (i.e., starti <= newEnd and endi >= newStart), merge the overlapping intervals by updating newInterval to the merged boundaries.

Iterate over Intervals:

For each interval in the intervals array, if it does not overlap with newInterval, simply add it to the result.
If there is an overlap, merge the overlapping intervals by updating newInterval to:

newInterval[0] = min(newInterval[0], starti);
newInterval[1] = max(newInterval[1], endi);

Once the merging is complete, the resulting array will be sorted and non-overlapping.

Add Remaining Intervals:

If there are intervals after the position of the merged interval, append them to the result array.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> result; // Resultant array of intervals
    int i = 0, n = intervals.size();

    // Step 1: Add all intervals that come before the new interval
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push_back(intervals[i]);
        i++;
    }

    // Step 2: Merge overlapping intervals with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.push_back(newInterval); // Add the merged interval

    // Step 3: Add all intervals that come after the new interval
    while (i < n) {
        result.push_back(intervals[i]);
        i++;
    }

    return result;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {6, 9}};
    vector<int> newInterval = {2, 5};

    vector<vector<int>> result = insertInterval(intervals, newInterval);
    cout << "Resulting Intervals: ";
    for (const auto& interval : result) {
        cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    cout << endl;

    return 0;
}

Complexity Analysis

Time Complexity:
- Traversal through all intervals happens once: O(n), where n is the number of intervals.
- Merging overlapping intervals is constant time per iteration as only the current interval and newInterval are involved.
Total Time Complexity: O(n).
Space Complexity:
- Result is stored in a new vector: O(n).
- Space used for storing merged intervals (in the result).

Handling Edge Cases

Empty Intervals:
- intervals = [] and newInterval = [5, 7] → Result: [[5, 7]]. If the input list is completely empty, the result solely consists of the new interval.
No Overlap:
- intervals = [[1, 2], [3, 4]] and newInterval = [5, 6] → Result: [[1, 2], [3, 4], [5, 6]]. The new interval simply appends at the end.
Complete Overlap:
- intervals = [[1, 5]] and newInterval = [2, 3] → Result: [[1, 5]]. The new interval is entirely consumed by an existing interval.

Frequently Asked Questions (FAQ)

How do you insert a new interval into a sorted array of non-overlapping intervals?
To insert a new interval, traverse the sorted array and add all intervals that end before the new interval starts. Then, merge any overlapping intervals by updating the start and end times of the new interval. Finally, append the remaining intervals.

What is the time complexity of merging overlapping intervals?
The time complexity is O(n), where n is the number of intervals. This is because we only need to iterate through the given list of intervals exactly once to insert and merge them.

Why is the initial array of intervals required to be sorted?
A sorted array allows us to process the intervals linearly without needing an additional sorting step. It ensures that overlapping intervals are adjacent to the new interval's correct position, making the merge process highly efficient.

Can we use binary search to optimize the insertion?
While binary search can be used to find the insertion point in O(log n) time, the merging process and shifting of elements still require O(n) time. Therefore, the linear scan approach is preferred due to its simplicity and identical worst-case time complexity.