Leetcode 57: Insert Interval

1. Problem Statement (Simple Explanation)

You are given:

• A sorted array of non-overlapping intervals: intervals[i] = [start_i, end_i] sorted by start_i ascending.

• A new interval: newInterval = [start, end].

You must:

• Insert newInterval into intervals.

• Keep the array:

• sorted by start

• non-overlapping (merge where necessary)

• Return the resulting list (you can allocate a new array).

2. Examples

Example 1:

Input:

intervals = [[1,3],[6,9]]

newInterval = [2,5]

• [1,3] and [2,5] overlap → merge into [1,5].

• [6,9] does not overlap.

Output: [[1,5],[6,9]]

Example 2:

Input:

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

newInterval = [4,8]

Overlaps:

• [3,5] with [4,8]

• [6,7] with [4,8]

• [8,10] with [4,8]

All merged into one interval [3,10].

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

3. Approach – Linear Scan with Three Phases

Since intervals is sorted and non-overlapping, we can insert and merge in one pass.

We maintain a list result.

We will:

1. Add all intervals that end before the new interval starts (no overlap).

2. Merge all intervals that overlap with newInterval into an updated newInterval.

3. Add all intervals that start after the new interval ends.

Overlap Conditions:

Given current interval [s, e] and current newInterval = [ns, ne]:

• No overlap, current before new:

• e < ns

• No overlap, current after new:

• s > ne

• Overlap:

• Otherwise, we merge by: ns = min(ns, s) and ne = max(ne, e)

Pseudo-code:

Complexity:

Let n = intervals.length:

• Time: O(n) – single pass.

• Space: O(n) for result.

4. Java code

5. C code

6. C++ code

7. Python code

8. JavaScript code