Geek has an array of N non-overlapping intervals intervals where intervals[i] = [start_{i}, end_{i}] represent the start and the end of the i^{th} event and intervals is sorted in ascending order by start_{i}. He wants to add a new interval newEvent = [newStart, newEnd] where newStart and newEnd represent the start and end of this interval.
Help Geek to insert newEvent 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).
Example 1:
Input:
N = 3
intervals = [[1,3], [10,15], [20,30]]
newEvent = [5,6]
Output: [[1,3], [5,6], [10,15], [20,30]]
Explanation: The newEvent (5, 6) does not overlap with any of the existing ranges, hence it is added
to the intervals list maintaining the sorted order of start times.
Example 2:
Input:
N = 5
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newEvent = [5,10]
Output: [[1,2], [3,10], [12,16]]
Explanation: Because the new interval [5,10] overlaps with [3,5],[6,7],[8,10].

Your Task:
You don't need to read input or print anything. Your task is to complete the function insertNewEvent() which takes N, the list of intervals and newEvent as input and returns the final list of intervals after inserting the newEvent in the original list.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ start[i], end[i] ≤ 10^{9}

见题面

见题面