71. Insert Interval

You are given an array of non-overlapping intervals intervals sorted by start time, and a new interval newInterval. Insert newInterval into intervals (merging if necessary) so that the result remains sorted and non-overlapping. Return the updated intervals.

Input: A sorted non-overlapping intervals array and a new interval [start, end].

Output: Updated intervals array after insertion and merging.

Examples

Input: [[1,3],[6,9]],[2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps [1,3] → merge to [1,5]. [6,9] unchanged.

Input: [[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps [3,5],[6,7],[8,10] → merge all to [3,10].

Input: [],[5,7]
Output: [[5,7]]
Explanation: Empty intervals. Insert directly.

Constraints

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^5
• Intervals are non-overlapping and sorted by start.

Asked by