inserting intervals

Given array of non-overlapping intervals, we have interval[i] = [starting, ending] which is the start and end of given interval and the intervals is sorted in ascending order from start. We are also given an interval arr = [start, end] that represents the start and end of another interval.

Insert arr into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals we may also merge the intervals if necessary.

Return the interval array after the insertion.

Input Format

First Parameter - Matrix intervals of size m x n

Second Parameter - number n

Third Parameter - Array arr of size n

Output Format

Return the matrix

Example 1:

Input: interval = [[1,2],[3,5],[6,7],[8,10],[12,16]], arr = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: since the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= interval.length <= 104
• intervals[i].length == 2
• 0 <= starting<= ending <= 105
• Expected Time Complexity: O(n)
• Expected Auxiliary Space: O(n)