Insert Interval medium

Problem Statement

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Explanation: Because the new interval [2,5] overlaps with [1,3], the intervals are merged into [1,5].

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10], the intervals are merged into [3,10].

Steps

1. Initialization: Create a result vector merged to store the merged intervals.
2. Handle Intervals Before Overlap: Iterate through the input intervals until you find an interval that overlaps with newInterval. Add all non-overlapping intervals to merged.
3. Merge Overlapping Intervals: Once you find an overlap, start merging intervals. This involves updating the newInterval's start and end to encompass all overlapping intervals.
4. Handle Remaining Intervals: After processing all overlapping intervals, add the updated newInterval to merged.
5. Add Remaining Intervals: Add any remaining intervals from intervals to merged.

Explanation

The core idea is to identify the range of intervals that overlap with the newInterval. We iterate through the intervals and check for overlap using the condition: intervals[i][1] >= newInterval[0]. Once an overlap is detected, we merge by adjusting the newInterval's start and end to include the overlapping intervals until we reach an interval that doesn't overlap.

Code

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> merged;
    int i = 0;

    // Add all intervals ending before newInterval starts
    while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
        merged.push_back(intervals[i]);
        i++;
    }

    // Merge overlapping intervals
    while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = min(newInterval[0], intervals[i][0]);
        newInterval[1] = max(newInterval[1], intervals[i][1]);
        i++;
    }
    merged.push_back(newInterval);

    // Add remaining intervals
    while (i < intervals.size()) {
        merged.push_back(intervals[i]);
        i++;
    }

    return merged;
}

Complexity

• Time Complexity: O(N), where N is the number of intervals. We iterate through the intervals at most twice.
• Space Complexity: O(N) in the worst case, as we might need to store all the intervals in the merged vector. In the best case (no overlaps), it is O(N).