Insert Interval

openai Insert Interval Given a set of non-overlapping intervals arranged by their start times, insert a new interval into the list, ensuring that the intervals remain ordered and non-overlapping (merge intervals if necessary). Input A list of several intervals in the format [[start1, end1], [start2, end2], ...]. A new interval to be inserted, in the format [start, end]. Output Merged list of intervals. Example Input: intervals = [[1,3],[6,9]] newInterval = [2,5] Output: [[1,5],[6,9]] Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Constraints The length of intervals is [0, 10^4]. Any value in newInterval is within [-10^5, 10^5]. Example Input 1,3; 6,9|2,5