Link to Question

MEDIUM

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] sorted by start_i, and an interval newInterval.

Insert newInterval into intervals such that intervals is still sorted by start_i and non-overlapping (merge if necessary).

Return intervals after the insertion.

Example

Input:

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

Output:

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

Explanation:
The new interval [2,5] overlaps with [1,3], so they are merged into [1,5].

---

Constraints

• 0 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start_i ≤ end_i ≤ 10⁴
• 0 ≤ newInterval.length == 2
• 0 ≤ newInterval[0] ≤ newInterval[1] ≤ 10⁴

---

Solution: Sorting

• Time Complexity: O(n)
• Space Complexity: O(n)

C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int i = 0, n = intervals.size();
        // Add all intervals before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) res.push_back(intervals[i++]);
        // Merge all overlapping intervals
        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;
        }
        res.push_back(newInterval);
        // Add remaining intervals
        while (i < n) res.push_back(intervals[i++]);
        return res;
    }
};