57. Insert Interval

Intuition

Given a list of non-overlapping intervals sorted by their start times and a new interval, the task is to insert the new interval into the list and merge any overlapping intervals. The list should remain sorted and non-overlapping after the insertion.

Approach

1. Initialization: Create two lists, left and right, to store intervals that are completely to the left and right of the new interval, respectively.
2. Iterate Through Intervals: Traverse the given list of intervals: - If the current interval ends before the new interval starts, it belongs to the left list. - If the current interval starts after the new interval ends, it belongs to the right list. - If there is an overlap, merge the intervals by updating the start to the minimum start and the end to the maximum end.
3. Combine Results: After processing all intervals, the left list contains all intervals before the new merged interval, and the right list contains all intervals after the new merged interval. Combine these lists with the new merged interval in between.
4. Return Result: Return the combined list of intervals.

Complexity

Time Complexity:

O(n), where n is the number of intervals. The list is traversed once to place intervals in left and right lists and merge overlaps.

Space Complexity:

O(n) for the additional lists left and right, where n is the number of intervals. The space used for the result is proportional to the number of intervals.

Code

C++

class Solution {
public:
    vector> insert(vector>& intervals, vector& newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];
        vector> left, right;
        for (const auto& interval : intervals) {
            int first = interval[0];
            int last = interval[1];
            if (last < start) {
                left.push_back(interval);
            } else if (first > end) {
                right.push_back(interval);
            } else {
                start = min(start, first);
                end = max(end, last);
            }
        }
        left.push_back({start, end});
        left.insert(left.end(), right.begin(), right.end());
        return left;
    }
};

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        start, end = newInterval
        left, right = [], []
        for first, last in intervals:
            if last < start:
                left.append([first, last])
            elif first > end:
                right.append([first, last])
            else:
                start = min(start, first)
                end = max(end, last)
                
        return left + [[start, end]] + right

Java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0];
        int end = newInterval[1];
        List left = new ArrayList<>();
        List right = new ArrayList<>();
        for (int[] interval : intervals) {
            int first = interval[0];
            int last = interval[1];
            if (last < start) {
                left.add(interval);
            } else if (first > end) {
                right.add(interval);
            } else {
                start = Math.min(start, first);
                end = Math.max(end, last);
            }
        }
        List result = new ArrayList<>(left);
        result.add(new int[]{start, end});
        result.addAll(right);
        return result.toArray(new int[result.size()][]);
    }
}

JavaScript

var insert = function (intervals, newInterval) {
  let [start, end] = newInterval;
  let left = [];
  let right = [];
  for (const interval of intervals) {
    const [first, last] = interval;
    if (last < start) left.push(interval);
    else if (first > end) right.push(interval);
    else {
      start = Math.min(start, first);
      end = Math.max(end, last);
    }
  }
  return [...left, [start, end], ...right]; 
};