Insert Interval: the idea to remember.

The core insight

Append intervals ending before the new one. Merge every overlap into a growing interval, then append the remaining suffix.

Why it works

Sorted disjoint input ensures that all overlaps are contiguous; after the first later interval, no future interval can overlap.

The mistake to avoid

Closed intervals touching at an endpoint merge. Keep the before test strict and the overlap test inclusive.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int[][] insert(int[][] intervals, int[] add) {
    List<int[]> out = new ArrayList<>(); int i = 0;
    while (i < intervals.length && intervals[i][1] < add[0]) out.add(intervals[i++]);
    int start = add[0], end = add[1];
    while (i < intervals.length && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]); end = Math.max(end, intervals[i++][1]);
    }
    out.add(new int[]{start, end});
    while (i < intervals.length) out.add(intervals[i++]);
    return out.toArray(new int[0][]);
}

Make the next connection