Insert Interval in C#

You are given an array of intervals, where intervals[i] = [starti, endi], sorted by their start, no two of which overlap, and one more interval, newInterval = [start, end].

Insert newInterval into intervals, merging it with every interval it overlaps, and return an array of the intervals after the insertion: still sorted by their start, with no two of them overlapping.

Two intervals overlap when they share at least one point. Intervals that only touch, like [1,4] and [4,5], share the point 4, so they overlap too and merge into [1,5].

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps [1,3], so they merge into [1,5]. [6,9] starts after 5, so it stays as it is.

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: [4,8] overlaps [3,5] and [6,7], and it touches [8,10] at 8, so all four merge into [3,10].

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: There is nothing to merge with, so the answer holds only the new interval.

Constraints:

• 0 <= intervals.length <= 105
• 0 <= starti <= endi <= 106
• intervals is sorted by start, and endi < starti+1: no two intervals overlap or touch.
• 0 <= start <= end <= 106