1444. Taking One Whole Schedule Out of Another

Two schedules are given, each as HALF-OPEN intervals [a, b), each already sorted by start and already tidy: within one schedule no two intervals overlap and no two of them even touch.

Print the first schedule with everything the second schedule covers removed, still sorted and still tidy.

A = [1,10) [20,30) B = [3,5) [8,22) -> [1,3) [5,8) [22,30) A = [1,3) [6,9) B = [3,6) -> [1,3) [6,9) A = [0,10) B = [0,10) -> nothing left

The middle line is the endpoint rule. B's single stretch begins exactly where A's first interval ends and ends exactly where A's second begins. Half-open intervals that merely touch share no point, so A comes back untouched. Under a CLOSED reading the answer would be [1,3) shortened and [6,9) shortened, which is a different output entirely.

## What most people try first

Calling the single-hole routine from problem 1443 once per interval of B. That is correct and it rebuilds the whole of A every time, so with n and m both at 2 * 10^5 it is 4 * 10^10 interval copies.

The other attempt is to compute, for each interval of A, the intervals of B that meet it by scanning all of B. That is the same O(nm) from the other direction. Both schedules are SORTED, and neither attempt uses it.

## Walk both lists once

j = 0 for each [a, b) in A: cur = a the part of [a, b) not yet accounted for advance j while B[j].end <= cur those lie entirely before what is left while j < m and B[j].start < b: if B[j].start > cur: emit [cur, min(B[j].start, b)) cur = max(cur, B[j].end) if cur >= b: break j = j + 1 if cur < b: emit [cur, b)

j never moves backwards across the whole run, so the total work is O(n + m) after reading, and the output is produced in order.

## Why j never has to go back

Every interval of B that ends at or before the current position can never meet any later interval of A, because the intervals of A are sorted and disjoint, so every later one starts at or after the current position. That is the invariant the single forward pointer relies on, and it is the same argument that makes the two-pointer merge of two sorted lists work.

An interval of B that reaches past the end of the current A interval is NOT consumed, which is why j is only advanced inside the loop when the current B interval is finished with. Advancing it unconditionally is the common bug, and it loses the second half of B = [8,22) in the first sample.

## The boundary that breaks a careless implementation

The test for a piece surviving in front of a B interval is B[j].start > cur, strict. If B starts exactly at cur there is no piece to emit and an unguarded version emits [cur, cur), an empty interval. The same applies at the end: emit the tail only when cur < b.

## Overflow

Every coordinate is at most 10^9 in magnitude and nothing accumulates, so a signed 32 bit integer, limit 2147483647, holds every value here. Both schedules together hold at most 4 * 10^5 intervals and the output at most n + m, so the answer list cannot blow up either.

## Related

Problem 1443 removes ONE stretch and can afford a single pass over A alone. Problem 1438 walks two sorted lists to find where they INTERSECT; this walks the same two lists to find where the first one does not. Problem 1446 takes the complement inside a fixed window instead of against a second list.

Constraints - `0 ≤ n ≤ 200000` and `0 ≤ m ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` for every interval of either schedule - every interval is half-open, `[a, b)` - within each schedule the intervals are sorted by start, and each start is strictly greater than the previous end