Insert New Interval and Merge Overlapping Intervals

Given an array of non-overlapping intervals intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] represent the start and the end of the i<sup>th</sup> event and intervals is sorted in ascending order by start<sub>i</sub>. 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<sub>i</sub> and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

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⁹Try more examples

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.

---

Key Steps to Solve the Problem:

1. 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.
2. 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.
3. Preserve Sorting:
   • Since the given list is already sorted and we insert the new interval at the correct position, the list remains sorted.

---

Algorithm:

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

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 (i.e., starti <= newEnd and endi >= newStart), 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:

1. 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: O(n).
2. Space Complexity:
   • Result is stored in a new vector: O(n).
   • Space used for storing merged intervals (in the result).

---

Edge Cases:

1. Empty Intervals:
   • intervals = [] and newInterval = [5, 7] → Result: [[5, 7]].
2. No Overlap:
   • intervals = [[1, 2], [3, 4]] and newInterval = [5, 6] → Result: [[1, 2], [3, 4], [5, 6]].
3. Complete Overlap:
   • intervals = [[1, 5]] and newInterval = [2, 3] → Result: [[1, 5]].