Insert Interval

Share

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

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

Solution Approach

Three phases: add all intervals that end before the new interval; merge all overlapping intervals; add remaining.

  • Add all intervals where interval.end < newInterval.start.
  • Merge all overlapping: while intervals exist and interval.start <= newInterval.end, expand newInterval.
  • Add remaining intervals.
Java
import java.util.*;

class Solution {
    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]);
        }
        res.add(newInterval);
        while (i < n) res.add(intervals[i++]);
        return res.toArray(new int[0][]);
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)