Insert Interval [Medium] — Sweep and Merge

Problem Statement

Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.

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

Intuition

Three phases: copy non-overlapping intervals before new interval, merge overlapping ones with the new interval, copy the rest.

Solutions

C++

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> res;
    int i = 0, n = intervals.size();
    // Phase 1: before overlap
    while (i < n && intervals[i][1] < newInterval[0]) res.push_back(intervals[i++]);
    // Phase 2: merge overlapping
    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);
    // Phase 3: after overlap
    while (i < n) res.push_back(intervals[i++]);
    return res;
}

Java

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.add(newInterval);
    while (i < n) res.add(intervals[i++]);
    return res.toArray(new int[0][]);
}

JavaScript

var insert = function(intervals, newInterval) {
    const res = [];
    let i = 0;
    while (i < intervals.length && intervals[i][1] < newInterval[0]) res.push(intervals[i++]);
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.push(newInterval);
    while (i < intervals.length) res.push(intervals[i++]);
    return res;
};

Python

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    res, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        res.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
    res.append(newInterval)
    return res + intervals[i:]

Complexity

Time: O(n)
Space: O(n)