3.11 Insert Interval

3.11.1 Problem Metadata

3.11.2 Description

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

3.11.3 Examples

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

3.11.4 Constraints

  • 0 <= intervals.length <= 10^4
  • Intervals are non-overlapping and sorted

3.11.5 Solution - Linear Merge

3.11.5.1 Walkthrough

Iterate through intervals, appending those ending before the new interval. Merge overlapping intervals by expanding newInterval. Once the new interval ends before the current interval, append it and the rest.

3.11.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) output lc-list

3.11.5.3 Implementation Steps

  1. Initialize result lc-list and index i = 0.
  2. Append all intervals whose end < newInterval.start.
  3. While intervals overlap with newInterval, update start = min and end = max.
  4. Append the merged new interval.
  5. Append remaining intervals.

3.11.5.4 Code - Java

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

    int index = 0;
    //add all intervals before newInterval
    while(index < intervals.length && intervals[index][1] < newInterval[0]) {
        result.add(intervals[index]);
        index++;
    }

    //combine all intervals merged with newInterval
    while(index < intervals.length && intervals[index][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
        index++;
    }

    //add merged newInterval
    result.add(newInterval);

    //add remaining intervals after newInterval
    while(index < intervals.length) {
        result.add(intervals[index]);
        index++;
    }

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