Insert Intervals

Given a collection of non-overlapping intervals, represented as pairs of integers [start, end], where start denotes the start time of the interval and end denotes the end time of the interval, and a new interval [newStart, newEnd], insert the new interval into the existing intervals and merge overlapping intervals if necessary.

Example:

Input:

intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]

Output:

[[1, 5], [6, 9]]

Explanation: In the input, the new interval [2, 5] overlaps with the existing interval [1, 3]. So, they can be merged into [1, 5]. The other interval [6, 9] is already non-overlapping. Thus, the merged intervals after inserting [2, 5] are [[1, 5], [6, 9]].

Insert Intervals Solution in C++:

#include <iostream>
#include <vector>

// Function to insert and merge intervals
std::vector<std::vector<int>> insertInterval(std::vector<std::vector<int>>& intervals, std::vector<int>& newInterval) {
    std::vector<std::vector<int>> mergedIntervals;
    int i = 0;
    int n = intervals.size();

    // Add all intervals that end before the new interval starts
    while (i < n && intervals[i][1] < newInterval[0]) {
        mergedIntervals.push_back(intervals[i]);
        ++i;
    }

    // Merge overlapping intervals with the new interval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = std::min(newInterval[0], intervals[i][0]);
        newInterval[1] = std::max(newInterval[1], intervals[i][1]);
        ++i;
    }
    mergedIntervals.push_back(newInterval);

    // Add all intervals that start after the new interval ends
    while (i < n) {
        mergedIntervals.push_back(intervals[i]);
        ++i;
    }

    return mergedIntervals;
}

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

    std::vector<std::vector<int>> result = insertInterval(intervals, newInterval);

    std::cout << "Merged Intervals after insertion:\n";
    for (const auto& interval : result) {
        std::cout << "[" << interval[0] << ", " << interval[1] << "] ";
    }
    std::cout << std::endl;

    return 0;
}

Insert Intervals Explanation:

1. The insertInterval function takes a reference to a vector of vectors intervals and a reference to a vector newInterval.
2. We create a new vector mergedIntervals to store the merged intervals after inserting the new interval.
3. We initialize a variable i to 0, representing the index of the current interval in the intervals vector.
4. We iterate through the intervals vector and add all intervals that end before the new interval starts (i.e., non-overlapping intervals before the new interval).
5. We then merge any overlapping intervals with the new interval. To do this, we continuously update the start and end time of the new interval using std::min and std::max functions while iterating through overlapping intervals.
6. After merging, we add the updated new interval to the mergedIntervals.
7. Finally, we add all intervals that start after the new interval ends (i.e., non-overlapping intervals after the new interval).

Time Complexity:

The time complexity of this solution is O(n), where n is the number of intervals in the input vector intervals. We perform a linear scan through the intervals vector to insert and merge the new interval.

Space Complexity:

The space complexity of this solution is O(n), where n is the number of intervals in the input vector intervals. This is because we create a new vector mergedIntervals to store the merged intervals. In the worst case, if there are no overlapping intervals, mergedIntervals will contain all intervals from the original vector.