57. Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

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).

Return intervals after the insertion.

Note that you don’t need to modify intervals in-place. You can make a new array and return it.

Example 1:

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

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].

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        vector<vector<int>> result;
        int i = 0;

        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }

        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);

        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

from typing import *

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        result = []
        i = 0

        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1

        result.append(newInterval)

        while i < n:
            result.append(intervals[i])
            i += 1

        return result

Time Complexity:

• Initial Traversal: \( O(n) \)
  • We iterate through the intervals list up to three times:
  • The first while loop runs in \( O(n) \) time, where \( n \) is the number of intervals, as it iterates through the list until it finds an interval that overlaps with newInterval.
  • The second while loop also runs in \( O(n) \) time, as it merges all overlapping intervals with newInterval.
  • The final while loop runs in \( O(n) \) time, as it adds the remaining intervals to the result list.
• Overall Time Complexity: \( O(n) \)

Since each interval is processed a constant number of times, the overall time complexity is \( O(n) \).

Space Complexity:

• Result List: \( O(n) \)

The space complexity is primarily determined by the space needed to store the result list, which can be at most \( n + 1 \) intervals in the worst case, where \( n \) is the number of original intervals.

• Overall Space Complexity: \( O(n) \)

Since the only additional space used is the result list, which can store up to \( n + 1 \) intervals, the overall space complexity is \( O(n) \).