Insert Interval

Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.

Function signature

func InsertInterval(intervals [][]int, newInterval []int) [][]int

Inputs / outputs

• intervals: sorted, non-overlapping intervals.
• newInterval: interval to insert.
• Return: updated list of merged intervals.

Example

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

Constraints

• 0 <= len(intervals) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

Split intervals into three parts:

1. Intervals completely before the new interval.
2. Intervals overlapping the new interval.
3. Intervals completely after the new interval.

Merge the overlapping ones into newInterval, then concatenate.

Algorithm (step-by-step)

1. Append all intervals that end before newInterval starts.
2. Merge all intervals that overlap newInterval, adjusting its start/end.
3. Append the merged newInterval.
4. Append the remaining intervals.

Correctness sketch

• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

Trace (hand walkthrough)

Example input:
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Walk:
- new [2,5] overlaps [1,3] -> merge to [1,5]
- append remaining [6,9] -> [[1,5],[6,9]]

Pitfalls to avoid

• Forgetting to append intervals after the merge.
• Incorrect overlap check (interval.start <= newEnd).

Complexity

• Time: O(n)
• Extra space: O(n) for output.

Implementation notes (Go)

• Append intervals that end before the new interval starts.
• Merge overlaps, then append remaining intervals.