Insert Interval

Statement

Given a sorted list of nonoverlapping intervals and a new interval, your task is to insert the new interval into the correct position while ensuring that the resulting list of intervals remains sorted and nonoverlapping. Each interval is a pair of nonnegative numbers, the first being the start time and the second being the end time of the interval.

Constraints:

• $0 \leq$ existing_intervals.length $\leq 10^4$

• existing_intervals[i].length, new_interval.length == 2

• $0 \leq$ start time $<$ end time $\leq 10^4$

• The list of intervals is sorted in ascending order based on the $start ~time$.