Insert Interval

---

Insert Interval: You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. 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 start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

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 <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^5
• intervals is sorted by start_i in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10^5

---

Try this Problem on your own or check similar problems:

1. Merge Intervals
2. Range Module

Solution:

Java

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int iterator = 0;

    while (iterator < intervals.length && intervals[iterator][1] < newInterval[0]) {
        result.add(intervals[iterator++]);
    }

    while (iterator < intervals.length && intervals[iterator][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[iterator][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[iterator][1]);
        ++iterator;
    }

    result.add(newInterval);

    while (iterator < intervals.length){
        result.add(intervals[iterator++]);
    }

    return result.toArray(new int[result.size()][]);
}

JavaScript

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const result = [];
  let iterator = 0;

  while (
    iterator < intervals.length &&
    intervals[iterator][1] < newInterval[0]
  ) {
    result.push(intervals[iterator++]);
  }

  while (
    iterator < intervals.length &&
    intervals[iterator][0] <= newInterval[1]
  ) {
    newInterval[0] = Math.min(newInterval[0], intervals[iterator][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[iterator][1]);
    iterator++;
  }

  result.push(newInterval);

  while (iterator < intervals.length) {
    result.push(intervals[iterator++]);
  }

  return result;
};

Python

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

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

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

        result.append(newInterval)

        while iterator < len(intervals):
            result.append(intervals[iterator])
            iterator += 1

        return result

C++

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        std::vector<std::vector<int>> result;
        int iterator = 0;

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

        while (iterator < intervals.size() && intervals[iterator][0] <= newInterval[1]) {
            newInterval[0] = std::min(newInterval[0], intervals[iterator][0]);
            newInterval[1] = std::max(newInterval[1], intervals[iterator][1]);
            iterator++;
        }

        result.push_back(newInterval);

        while (iterator < intervals.size()) {
            result.push_back(intervals[iterator]);
            iterator++;
        }

        return result;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

We broke the problem into three parts:

• We first iterate over all the intervals that come before our new interval (in other words their ends are before the start of our new interval) and we add them to the result list.
• We found the first intersection and we keep on merging the intervals as long as there are intervals in the input array, and we have an intersection (start of the interval is before the end our newInterval). Each time we merge intervals we take the lower start and higher end time. Finally, when we exit the loop, we add the new merged interval.
• We keep on iterating until there are no more elements in the input array (the original array of intervals).

How do we can make sure there's intersection in the second loop? Well, if we already know that the end of the current interval comes after the start of our newInterval, we only must make sure that start of the current interval is before the end of the newInterval. For each next interval we know already that its start is after the minimum start of our merged interval because of the sorted order of the array, we only must make sure it's before the (maximum) end time of our merged interval.