Quick Overview

Compute available deployment windows by merging allowed and blocked half-open intervals, subtracting overlaps, and returning maximal sorted nonempty ranges.

Subtract Blocked Periods from Allowed Deployment Windows

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Online Assessment

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 ```text allowed = [[1,10],[8,14],[20,25]] blocked = [[3,5],[12,22]] result = [[1,3],[5,12],[22,25]] ``` ```text 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. ```hint Normalize before subtracting Once each input represents a disjoint sorted union, a blocked interval can be advanced monotonically across the allowed windows. ```

Overview: Compute available deployment windows by merging allowed and blocked half-open intervals, subtracting overlaps, and returning maximal sorted nonempty ranges.

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 ```text allowed = [[1,10],[8,14],[20,25]] blocked = [[3,5],[12,22]] result = [[1,3],[5,12],[22,25]] ``` ```text 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. ```hint Normalize before subtracting Once each input represents a disjoint sorted union, a blocked interval can be advanced monotonically across the allowed windows. ```

Constraints

  • Each list contains at most 100000 half-open intervals.
  • Integer endpoints satisfy 0 <= start < end <= 1000000000.
  • Inputs may be empty, unsorted, overlapping, duplicated, or touching.
  • Return the allowed union minus the blocked union as sorted maximal nonempty intervals.

Examples

Input: ([[1, 10], [8, 14], [20, 25]], [[3, 5], [12, 22]])

Expected Output: [[1, 3], [5, 12], [22, 25]]

Explanation: Normalize overlapping allowed intervals, then subtract two blocked spans.

Input: ([[0, 2], [2, 4]], [[4, 7]])

Expected Output: [[0, 4]]

Explanation: Touching allowed windows merge; a blocker beginning at the half-open end has no effect.

Loading coding console...

Show the approach

Approach

Sort each input by start and merge intervals whose next start is at most the current end. Merging equality preserves their half-open union and eliminates adjacent output fragments. Scan normalized allowed windows while retaining a monotone pointer into the normalized blocked union. For each allowed window, a cursor marks its first not-yet-handled point. Skip blockers ending at or before the cursor; these cannot block it. A blocker beginning before the allowed end either yields the available gap before it or immediately advances the cursor past blocked time. If a blocker reaches beyond this allowed window, keep its pointer for the next window: it may cover multiple separated allowed windows. Emit a final tail only when cursor is strictly before end. The invariant is that emitted pieces are exactly the unblocked prefix of processed allowed coverage. Normalization and the strict half-open intersection checks ensure these pieces are nonempty, sorted, and maximal. Each blocker is advanced at most once, with at most one retained blocker per allowed window, so subtraction is linear after sorting. No deployment duration or additional scheduling objective is introduced.

Time complexity:
O(A log A + B log B + A + B), within O((A+B) log(A+B)).
Space complexity:
O(A+B) for normalized unions and output.