When the dock and the driver are both free

Scenario

A Kestrel Freight hub loads trucks at its docks. A loading dock is free between the trucks it serves, and a driver is free between runs. Planning keeps each schedule as a list of free slots, sorted by time. Within one list, slots never overlap, but one slot may end at the very minute the next one begins.

A truck can load only when its dock and its driver are both free. For one dock and one driver, planning wants every period when both are free. Times are minutes from the start of the planning year, which has 525,600 minutes. A period of zero minutes is no use, because no truck loads in no time.

Your task

Write free_together(dock, driver).

dock[i] = [start, end] is a free slot of the dock, with start < end. The dock is free from minute start up to, but not including, minute end.
The slots in dock are sorted by time and do not overlap: each slot ends at or before the minute the next one starts.
driver holds the driver's free slots, in the same form and with the same rules.
Return every period when both are free, as [start, end] with the same meaning, sorted by time.
A dock slot and a driver slot share the period from the later of their starts to the earlier of their ends. Keep it only if it lasts at least one minute: start < end.
Slots that only touch, where one ends at the minute the other starts, share no time and give no period.
Do not join periods. Two periods that touch are returned as two periods.
If either list is empty, or no period exists, return an empty list.

Examples

Example 1 (traced)#

text2 lines

Input:  dock = [[480, 510], [525, 570], [600, 630]], driver = [[500, 530], [540, 550], [560, 600]]
Output: [[500, 510], [525, 530], [540, 550], [560, 570]]

i	j	dock[i]	driver[j]	Shared	Kept?	Ends first
0	0	[480, 510]	[500, 530]	[500, 510]	yes	the dock slot: i moves
1	0	[525, 570]	[500, 530]	[525, 530]	yes	the driver slot: j moves
1	1	[525, 570]	[540, 550]	[540, 550]	yes	the driver slot: j moves
1	2	[525, 570]	[560, 600]	[560, 570]	yes	the dock slot: i moves
2	2	[600, 630]	[560, 600]	[600, 600]	no: zero minutes	the driver slot: j moves

Minute 480 is 08:00 on the first day. The dock slot [525, 570] holds three shared periods. The last pair only touches at minute 600, so it gives no period.

Example 2#

text2 lines

Input:  dock = [[0, 60], [120, 180]], driver = [[60, 120], [180, 240]]
Output: []

The driver is free exactly when the dock is busy. Every pair of slots touches, and none overlaps.

Example 3#

text2 lines

Input:  dock = [[100, 200]], driver = []
Output: []

The driver has no free slot, so no truck can load.

Constraints

0 ≤ dock.length ≤ 5 × 10^4 and 0 ≤ driver.length ≤ 5 × 10^4
0 ≤ start < end ≤ 525,600 for every slot
In each list, slots[k][1] ≤ slots[k + 1][0] for every k: sorted, and never overlapping

What does n ≤ 5 × 10^4 tell you?

Comparing every dock slot with every driver slot is O(n × m). With 5 × 10^4 slots in each list, that is 2.5 × 10^9 pairs: far over the budget of about 10^8 simple operations a second. Aim for O(n + m).

Both lists are sorted, and within each list the slots do not overlap. That is the signal for two pointers, one in each list.

Read the values too. Times go up to 525,600 minutes, so 32-bit integers are enough.

Scenario

Your task

Write free_together(dock, driver).

dock[i] = [start, end] is a free slot of the dock, with start < end. The dock is free from minute start up to, but not including, minute end.
The slots in dock are sorted by time and do not overlap: each slot ends at or before the minute the next one starts.
driver holds the driver's free slots, in the same form and with the same rules.
Return every period when both are free, as [start, end] with the same meaning, sorted by time.
A dock slot and a driver slot share the period from the later of their starts to the earlier of their ends. Keep it only if it lasts at least one minute: start < end.
Slots that only touch, where one ends at the minute the other starts, share no time and give no period.
Do not join periods. Two periods that touch are returned as two periods.
If either list is empty, or no period exists, return an empty list.

Examples

Example 1 (traced)#

text2 lines

Input:  dock = [[480, 510], [525, 570], [600, 630]], driver = [[500, 530], [540, 550], [560, 600]]
Output: [[500, 510], [525, 530], [540, 550], [560, 570]]

i	j	dock[i]	driver[j]	Shared	Kept?	Ends first
0	0	[480, 510]	[500, 530]	[500, 510]	yes	the dock slot: i moves
1	0	[525, 570]	[500, 530]	[525, 530]	yes	the driver slot: j moves
1	1	[525, 570]	[540, 550]	[540, 550]	yes	the driver slot: j moves
1	2	[525, 570]	[560, 600]	[560, 570]	yes	the dock slot: i moves
2	2	[600, 630]	[560, 600]	[600, 600]	no: zero minutes	the driver slot: j moves

Minute 480 is 08:00 on the first day. The dock slot [525, 570] holds three shared periods. The last pair only touches at minute 600, so it gives no period.

Example 2#

text2 lines

Input:  dock = [[0, 60], [120, 180]], driver = [[60, 120], [180, 240]]
Output: []

The driver is free exactly when the dock is busy. Every pair of slots touches, and none overlaps.

Example 3#

text2 lines

Input:  dock = [[100, 200]], driver = []
Output: []

The driver has no free slot, so no truck can load.

Constraints

0 ≤ dock.length ≤ 5 × 10^4 and 0 ≤ driver.length ≤ 5 × 10^4
0 ≤ start < end ≤ 525,600 for every slot
In each list, slots[k][1] ≤ slots[k + 1][0] for every k: sorted, and never overlapping

What does n ≤ 5 × 10^4 tell you?

Both lists are sorted, and within each list the slots do not overlap. That is the signal for two pointers, one in each list.

Read the values too. Times go up to 525,600 minutes, so 32-bit integers are enough.