Robert Baindourov

NodeJS, ReactJS, ElectronJS - Web Software Architect

Given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith event and intervals is sorted in ascending order by starti. 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 starti 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]].