Дан массив непересекающихся интервалов intervals, где intervals[i] = [start_i, end_i] представляет начальное и конечное время i-го интервала. Интервалы изначально отсортированы в порядке возрастания по start_i.

Дан еще один интервал newInterval = [start, end]. Вставьте newInterval в intervals так, чтобы intervals все еще был отсортирован в порядке возрастания по start_i, и чтобы интервалы по-прежнему не пересекались. При необходимости можно объединять пересекающиеся интервалы.

Ограничения

• 0 <= intervals.length <= 1000
• newInterval.length == intervals[i].length == 2
• 0 <= start <= end <= 1000

intervals = [[1,3],[6,9]], newInterval = [2,5]

[[1,5],[6,9]]

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

[[1,2],[3,10],[12,16]]