Insert Interval

You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [start_i, end_i]` sorted in ascending order by `start_i`. You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval. Insert `newInterval` 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). Return `intervals` after the insertion. ### Constraints - `0 <= intervals.length <= 10^4` - `intervals[i].length == 2` - `0 <= start_i <= end_i <= 10^5` - `intervals` is sorted by `start_i` in ascending order. - `newInterval.length == 2` - `0 <= start <= end <= 10^5` ### Input Format - Line 1: An integer `n` representing the number of intervals. - The next `n` lines: Two space-separated integers `start end`. - The last line: Two space-separated integers representing `newInterval`. ### Output Format Print each merged interval on a new line as two space-separated integers.