Shared time of two schedules
Find the stretches when two people are both free, given each person's sorted list of free ranges, by walking both lists with two pointers. About 22 minutes.
Overlap of two ranges
Two people each have a sorted list of free ranges [start, end], with ends included and no two ranges in a list touching. You want the stretches when both are free.
For two ranges, the shared part starts at the later of the two starts and ends at the earlier of the two ends. If that start is after that end, the ranges do not overlap at all.
Advance the one that ends first
Keep one pointer in each list. Compute the shared part of the two current ranges and save it if it exists.
Then move on from whichever range ends first. It cannot overlap anything further along in the other list, because everything there starts later. If both end together, move either. Each step advances one pointer, so the work is linear in the two list sizes.
lo = max(a[0], b[0]) hi = min(a[1], b[1]) overlap = lo <= hi
[1, 4] and [3, 8] share [3, 4]. [1, 4] ends first, so move the first list on.
Ranges [1, 4] and [5, 8]. What do they share?
- ANothing
- BA single point
- C[1, 8]
Show the answer
Nothing. The later start 5 is after the earlier end 4.
Shared free time
You are given two lists, firstList and secondList, of ranges [start, end] with both ends included. Each list is sorted and its ranges do not overlap or touch. Return the list of ranges that are shared by both lists, in sorted order. A shared range may be a single point.
firstList = [[0, 2], [5, 10]], secondList = [[1, 5], [8, 12]] → [[1, 2], [5, 5], [8, 10]]
0 ≤ lengths ≤ 1,000 · 0 ≤ start ≤ end ≤ 1,000,000,000