LC 57 — Problem

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the i-th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end]. Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.

Input: intervals = 12,35,67,810,1216, newInterval = 48
Output: 12,310,1216
Input: intervals = 13,69, newInterval = 25
Output: 15,69

Constraints: 0 ≤ intervals.length ≤ 10⁴ · intervals[i].length == 2 · newInterval.length == 2

You have a sorted list of non-overlapping intervals and need to insert 48. What's your first instinct?

FIG. 1 — SORTED INTERVALS ON A NUMBER LINE
024681012141618[1,2][3,5][6,7][8,10][12,16]
New interval:[4,8]