Insert Interval

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 ≤ existing_intervals.length ≤ 10⁴
• existing_intervals[i].length, new_interval.length == 2
• 0 ≤ start time < end time ≤ 10⁴
• The list of intervals is sorted in ascending order based on the start time.

Examples

Example 1

Input:

• Existing intervals: [1, 3], [5, 7], [8, 9], [10, 13]
• New interval: [2, 6]

Explanation: We will merge [2, 6] with the first interval, [1, 3], to create [1, 6], and then merge this interval with the next overlapping interval, [5, 7], to create [1, 7]. The intervals [8, 9] and [10, 13] don't overlap with any intervals, so they will exist independently.

Output: [1, 7], [8, 9], [10, 13]

Example 2

Input:

• Existing intervals: [1, 3], [6, 9]
• New interval: [2, 5]

Explanation: We will merge [2, 5] with the first interval, [1, 3], since they overlap, to create a new interval [1, 5]. The interval [6, 9] will exist independently, since it doesn't overlap with the other interval.

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