Insert a new slot and merge

Scenario

An ad platform keeps a schedule of campaign flights for one advertiser. A flight is a range of days [start, end], including both days. The flights are sorted by start, and no two share a day, so the schedule has no overlaps.

The advertiser books one more flight. If it shares a day with existing flights, they must all be joined with it into one flight. Return the new schedule, still sorted.

Your task

Write add_slot(slots, new_slot).

slots is sorted by start. No two slots share a day, so they do not overlap and do not touch.
new_slot = [start, end] with start <= end. It may overlap or touch any number of slots.
Return the schedule after adding it, with every group of slots that share a day joined into one.

Examples

Example 1 (traced)#

text2 lines

Input:  slots = [[1, 2], [4, 5], [7, 9], [12, 15]], new_slot = [5, 8]
Output: [[1, 2], [4, 9], [12, 15]]

Work in three parts: copy the slots that end before the new slot, absorb the slots that overlap it, and copy the rest.

Slot	Part	What happens
[1, 2]	before	ends at 2, before 5: copy
[4, 5]	overlap	4 ≤ 8 and ends at 5: absorb, start 4, end 8
[7, 9]	overlap	7 ≤ 8: absorb, end 9
[12, 15]	after	starts at 12, after 9: copy

The absorbed slots and the new slot give [4, 9].

Example 2#

text2 lines

Input:  slots = [[5, 6]], new_slot = [1, 2]
Output: [[1, 2], [5, 6]]

The new slot ends before the only slot starts, so it goes first.

Example 3#

text2 lines

Input:  slots = [[1, 3], [5, 8]], new_slot = [4, 5]
Output: [[1, 3], [4, 8]]

Day 5 is in both [4, 5] and [5, 8], so they join. Day 4 is not in [1, 3].

Constraints

0 ≤ slots.length ≤ 100,000
0 ≤ start ≤ end ≤ 1,000,000,000 (days)
slots is sorted, and no two slots share a day.

What does n ≤ 10^5 tell you?

Joining overlapping pairs by repeated search costs about n × n. The schedule is already sorted, so one pass over it costs only n. You do not need to sort again.

Scenario

The advertiser books one more flight. If it shares a day with existing flights, they must all be joined with it into one flight. Return the new schedule, still sorted.

Your task

Write add_slot(slots, new_slot).

slots is sorted by start. No two slots share a day, so they do not overlap and do not touch.
new_slot = [start, end] with start <= end. It may overlap or touch any number of slots.
Return the schedule after adding it, with every group of slots that share a day joined into one.

Examples

Example 1 (traced)#

text2 lines

Input:  slots = [[1, 2], [4, 5], [7, 9], [12, 15]], new_slot = [5, 8]
Output: [[1, 2], [4, 9], [12, 15]]

Work in three parts: copy the slots that end before the new slot, absorb the slots that overlap it, and copy the rest.

Slot	Part	What happens
[1, 2]	before	ends at 2, before 5: copy
[4, 5]	overlap	4 ≤ 8 and ends at 5: absorb, start 4, end 8
[7, 9]	overlap	7 ≤ 8: absorb, end 9
[12, 15]	after	starts at 12, after 9: copy

The absorbed slots and the new slot give [4, 9].

Example 2#

text2 lines

Input:  slots = [[5, 6]], new_slot = [1, 2]
Output: [[1, 2], [5, 6]]

The new slot ends before the only slot starts, so it goes first.

Example 3#

text2 lines

Input:  slots = [[1, 3], [5, 8]], new_slot = [4, 5]
Output: [[1, 3], [4, 8]]

Day 5 is in both [4, 5] and [5, 8], so they join. Day 4 is not in [1, 3].

Constraints

0 ≤ slots.length ≤ 100,000
0 ≤ start ≤ end ≤ 1,000,000,000 (days)
slots is sorted, and no two slots share a day.

What does n ≤ 10^5 tell you?

Joining overlapping pairs by repeated search costs about n × n. The schedule is already sorted, so one pass over it costs only n. You do not need to sort again.