1. Problem Summary

You are given:

• a list of non-overlapping intervals
• the intervals are sorted by start time
• a new interval that must be inserted into the list

Your task is to:

1. Insert the new interval into the list
2. Merge any overlapping intervals that result
3. Return the final list of intervals

Example interpretation:
If the existing intervals are [[1,3], [6,9]] and the new interval is [2,5], after inserting and merging, the output becomes [[1,5], [6,9]].

---

2. Key Insights

The original intervals are already:

• non-overlapping
• sorted by starting time

This allows a linear scan.

Three logical phases occur:

1. Intervals that end before the new interval starts
2. Intervals that overlap with the new interval
3. Intervals that start after the merged interval ends

Overlapping rule

Two intervals overlap if:

current.start <= new.end
AND
current.end >= new.start

Merging rule

While overlapping:

new.start = min(new.start, current.start)
new.end   = max(new.end, current.end)

---

3. Approach

Linear traversal with merging

Steps:

1. Create an output list.
2. Traverse intervals while:
   • interval ends before new interval starts → add to output.
3. Continue traversal while intervals overlap:
   • merge them into the new interval.
4. Add the merged new interval.
5. Append remaining intervals.

This ensures ordering and correctness.

---

4. Time and Space Complexity

Time Complexity: O(N)

You pass through the interval list once.

Space Complexity: O(N)

Output list stores merged intervals.

---

5. Java Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Step 1: Add all intervals ending before newInterval begins
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Step 2: Merge all overlapping intervals
        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++;
        }

        // Add merged interval
        result.add(newInterval);

        // Step 3: Add remaining intervals
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

---

6. Dry Run Example

Input:

intervals = [[1,3], [6,9]]
newInterval = [2,5]

Step-by-step:

1. Compare [1,3] with [2,5]
   Overlap exists
   Merge → newInterval becomes [1,5]
2. Compare [6,9] with [1,5]
   No overlap since 6 > 5
   Stop merging
3. Add merged [1,5] to output
4. Append [6,9]

Final Output:

[[1,5], [6,9]]

---

Another Dry Run (more merging)

Input:

intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]]
newInterval = [4,8]

Processing:

• Skip [1,2] (ends before 4)
• [3,5] overlaps → merge to [3,8]
• [6,7] overlaps → merge to [3,8]
• [8,10] overlaps → merge to [3,10]
• Stop at [12,16]

Output:

[[1,2], [3,10], [12,16]]