#57 Insert Interval

Interval

Two Pointers

56.Insert Interval

Problem Statement:

Given a set of non-overlapping intervals and a new interval, insert the new interval at the correct position and merge all overlapping intervals if necessary. The intervals are sorted based on their start time.

Algorithm:

1. Add all intervals that end before newInterval starts
2. Merge overlapping intervals with newInterval
3. Add the merged newInterval
4. Add remaining intervals

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

    // Add all intervals that come before newInterval
    while (i < intervals.length && newInterval[0] > intervals[i][1])
        res.add(intervals[i++]);

    // Merge all overlapping intervals into newInterval
    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++;
    }

    // Add the merged interval
    res.add(newInterval);

    // Add remaining intervals that come after newInterval
    while (i < intervals.length) 
        res.add(intervals[i++]);
    
    return res.toArray(new int[res.size()][]);
}

Complexity:

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