Given a list of non-overlapping, sorted intervals represented as pairs [left_i, right_i], and a new interval [left_new, right_new], insert the new interval into the list such that the resulting list remains sorted and non-overlapping (merging intervals if necessary). Return the resulting list of intervals.
Example 1
Input: interval_list=[[2,4],[7,8]], interval_new=[5,6]
Output: [[2,4],[5,6],[7,8]]
Explanation: The new interval does not overlap with any existing intervals.
Example 2
Input: interval_list=[[1,3],[5,7],[9,12]], interval_new=[6,10]
Output: [[1,3],[5,12]]
Explanation: The new interval overlaps with [5,7] and [9,12], so they are merged.
Example 3
Input: interval_list=[], interval_new=[0,1]
Output: [[0,1]]
Explanation: Empty interval list, so just insert the new interval.
Constraints
Case 1
Input: interval_list=[[10,12],[15,18]], interval_new=[13,14]
Expected: [[10,12],[13,14],[15,18]]
Case 2
Input: interval_list=[[2,5],[7,9]], interval_new=[1,3]
Expected: [[1,5],[7,9]]
Case 3
Input: interval_list=[[1,2],[3,4],[5,6]], interval_new=[2,5]
Expected: [[1,6]]
Case 4
Input: interval_list=[[1,5]], interval_new=[0,0]
Expected: [[0,0],[1,5]]
Case 5
Input: interval_list=[[1,5]], interval_new=[6,8]
Expected: [[1,5],[6,8]]