Inserting Intervals

You are given a sorted list of non-overlapping intervals, and a new interval to insert. Your task is to merge the new interval with any overlapping intervals in the existing list, and then return the updated list of non-overlapping intervals. This is a common problem in scheduling, resource allocation, and data processing where intervals need to be consolidated.

Problem Description

Given a list of intervals, where each interval is represented as a pair of numbers [start, end], and a new interval [newStart, newEnd]. The original list of intervals is guaranteed to be sorted by their start times and are non-overlapping.

You need to insert the newInterval into this list and merge it with any existing intervals that overlap with it. The final output should be a list of intervals that are still sorted by start times and remain non-overlapping after the insertion and merging process.

Key Requirements:

• The input list of intervals is sorted by start times.
• The original intervals are non-overlapping.
• The newInterval must be inserted and potentially merged.
• The output list must also be sorted by start times and non-overlapping.

Expected Behavior: If the newInterval overlaps with one or more existing intervals, they should be merged into a single larger interval. The start of the merged interval will be the minimum of the start times of all overlapping intervals (including the newInterval), and the end will be the maximum of the end times.

Edge Cases to Consider:

• The newInterval does not overlap with any existing intervals.
• The newInterval overlaps with multiple consecutive intervals.
• The newInterval is completely contained within an existing interval.
• The newInterval completely engulfs one or more existing intervals.
• The input list of intervals is empty.

Examples

Example 1:

Input:
intervals = [[1,3],[6,9]]
newInterval = [2,5]

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

Explanation:
The new interval [2,5] overlaps with [1,3]. They merge to form [1,5].
The interval [6,9] does not overlap with the merged interval.

Example 2:

Input:
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]

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

Explanation:
The new interval [4,8] overlaps with [3,5], [6,7], and [8,10].
These three intervals and the new interval merge into a single interval [3,10].
The intervals [1,2] and [12,16] remain unchanged.

Example 3:

Input:
intervals = []
newInterval = [5,7]

Output:
[[5,7]]

Explanation:
The original list is empty, so the new interval is simply added.

Constraints

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
• intervals is sorted by intervals[i][0].
• intervals[i] and intervals[j] are non-overlapping for i != j.
• newInterval.length == 2
• 0 <= newInterval[0] <= newInterval[1] <= 10^5

Notes

Consider iterating through the existing intervals. You'll need to handle three main cases: intervals that come before the newInterval and do not overlap, intervals that overlap with the newInterval, and intervals that come after the newInterval and do not overlap. Pseudocode might involve using pointers or indices to manage the insertion and merging process efficiently.