1445. How Much of the Two Schedules Overlap

Two people each hand in a list of busy intervals. Each interval is CLOSED and written a b, covering everything from a to b inclusive, with a <= b. Neither list is sorted, and a list may contain intervals that overlap each other or repeat.

Print the total LENGTH of the part of the line at which both people are busy.

A = [1,6] [8,12] B = [4,9] [11,20] -> 4 A = [1,3] B = [3,5] -> 0 they meet at one point, which has no length A = [5,5] [7,7] B = [0,10] -> 0 two single points inside a long stretch

Work the first line through. A is busy on [1,6] and [8,12]; B is busy on [4,9] and [11,20]. Both are busy on [4,6], length 2, on [8,9], length 1, and on [11,12], length 1. Two plus one plus one is 4.

The second and third lines are the point of the problem. A single shared POINT is a real intersection and has length zero, so intervals that only touch, and intervals of zero width, contribute nothing to the answer even though they do intersect.

## What most people try first

Comparing every interval of A with every interval of B and adding max(0, min(b1, b2) - max(a1, a2)). That is the right formula for one pair and the wrong total for two families, because a stretch covered by two intervals of A and one of B is counted twice. With both lists at 2 * 10^5 it is also 4 * 10^10 pairs.

## Normalise each side first, then walk both

merge A into tidy runs; merge B into tidy runs (sort by start, sweep) i = 0, j = 0, total = 0 while i < |A| and j < |B|: lo = max(A[i].start, B[j].start) hi = min(A[i].end, B[j].end) if hi > lo: total += hi - lo advance whichever of A[i], B[j] ENDS first

O(n log n + m log m) for the two sorts, then one linear pass.

## Why advancing the one that ends first is right

The run that ends first cannot meet anything later in the other list, because the other list is sorted and everything still to come there starts at or after the run currently being looked at. So retiring it loses nothing. If both end at the same coordinate, either may be retired: whichever stays will be compared against the next run of the other list, and that comparison yields hi <= lo.

Merging each side first is what makes the double counting impossible. After the merge, no two runs of A share a point, so every position of the answer lies in exactly one run of A and exactly one run of B and is added once.

## The boundary that breaks a careless implementation

The test is hi > lo, strictly. Using hi >= lo adds zero, so it is harmless for the total, but it also makes an ordinary implementation add a phantom entry if it is later changed to print the shared stretches. The real trap is the opposite one: computing hi - lo + 1, the count of whole positions, which turns a single shared point into 1 and reports 3 rather than 0 on the third sample.

Note also that merging A must use a <= end, not a < end: two closed intervals sharing one point are one run.

## Overflow

Coordinates reach 10^9 either way, so the answer is at most 2 * 10^9, which FITS in a signed 32 bit integer since the limit is 2147483647. The raw sum of all interval lengths does not: 2 * 10^5 intervals of length 2 * 10^9 reach 4 * 10^14. Accumulate in 64 bit.

## Related

Problem 1438 walks two lists that are ALREADY sorted and tidy and prints each shared stretch. This one is handed two messy lists and asks only for the total length, so the normalising pass is the work and the touching case answers 0 rather than printing a zero-length line. Problem 1440 is the same normalising pass over one list.

Constraints - `1 ≤ n ≤ 200000` and `1 ≤ m ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` for every interval of either list - each interval is the closed stretch `[a, b]`, so `a == b` is a single point of length zero - neither list is sorted, and intervals within one list may overlap or repeat