Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary. Return the resulting list.
Input: intervals=[[1,3],[6,9]], newInterval=[2,5] → Output: [[1,5],[6,9]]Input: intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4,8] → Output: [[1,2],[3,10],[12,16]]
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.
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)