Insert an interval
intervals is a list of [start, end] pairs, both ends included, sorted by start. No two of them share a number. You get one more pair, new_interval.
Put it into the list. Every interval that shares at least one number with it joins it, and together they become one interval from the smallest of their starts to the largest of their ends. Sharing only an endpoint counts, so [1, 2] and [2, 4] become [1, 4]. Return the resulting list of [start, end] lists, still sorted by start, with no two intervals sharing a number.
intervals = [[1, 2], [4, 6], [8, 10]], new_interval = [5, 8]Output[[1, 2], [4, 10]][5, 8] shares 5 through 6 with [4, 6] and the number 8 with [8, 10], so all three become [4, 10].
intervals = [[1, 3], [7, 9]], new_interval = [4, 5]Output[[1, 3], [4, 5], [7, 9]]It shares nothing, so it goes in between, in start order.
intervals = [], new_interval = [2, 7]Output[[2, 7]]An empty list gets the new interval alone.
0 ≤ len(intervals) ≤ 104
0 ≤ start ≤ end ≤ 105
intervalsis sorted by start, and no two of its intervals share a number.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.