Subtract Blocked Periods from Allowed Deployment Windows

Given time intervals when deployment is allowed and intervals when it is blocked, return the remaining allowed deployment windows.

Implement available_deployment_windows(allowed: int[][], blocked: int[][]) -> int[][].

Constraints & Assumptions

The source names allowed and forbidden windows but omits the two assessment parts' exact contracts. This practice task is explicitly interval union/subtraction; it does not invent a deployment duration or another unreported scheduling objective.

• Each interval is [start,end) with integer endpoints, 0 <= start < end <= 1000000000.
• Each list has at most 100000 intervals. Inputs may be unsorted, overlap, contain duplicates, or touch at endpoints.
• A time is available if covered by at least one allowed interval and by no blocked interval. Blocks outside the allowed union have no effect.
• Return maximal nonempty available intervals sorted by start. Adjacent available intervals must be merged; zero-length fragments are omitted.
• Empty allowed input returns an empty list. Empty blocked input returns the merged allowed union.
• Aim for O((A+B) log(A+B)) time or better for A allowed and B blocked intervals.

Examples

allowed = [[1,10],[8,14],[20,25]]
blocked = [[3,5],[12,22]]
result = [[1,3],[5,12],[22,25]]

allowed = [[0,2],[2,4]], blocked = [[4,7]]
result = [[0,4]]

Explain interval normalization, half-open boundaries, a blocked interval spanning several allowed windows, and overlapping blocks. Clarify any additional duration, start-time, or multi-stage scheduling requirement before adding it.