Problem #57: Insert Interval

Intuition & Strategy Breakdown

Iterate through intervals: append all intervals ending before newInterval, merge overlapping intervals with newInterval, then append all remaining intervals.

Python Solution

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

Java Solution

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List 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[res.size()][]);
    }
}