Find deployable slots in a recurring week from allowed and freeze windows

A deployment scheduler works on a recurring week of 10,080 minutes (7 days of 24 hours of 60 minutes). Minute 0 is the start of the week, and the same schedule repeats every week. Teams declare windows in which deployments are allowed and windows in which deployments are frozen. A minute is deployable when it lies inside at least one allowed window and inside no freeze window, and a deployable slot is a maximal run of consecutive deployable minutes.

The exercise came in two parts. Part 1 takes only (start, end, type) windows and returns every deployable slot of the week. Part 2 adds the current UTC time, a lead time, a minimum slot length, a cap k on the number of slots, and a time-zone offset for each window. Implement Part 2. Part 1 is the special case utc_now = 0, lead_time_minutes = 0, min_continuous_minutes = 1, every offset = 0, and k at least the number of slots.

Function Signature

def deployable_slots(utc_now: int, lead_time_minutes: int, min_continuous_minutes: int, k: int, windows: list[tuple[int, int, str, int]]) -> list[list[int]]:

Rules

• Each window is (start, end, type, offset). start and end are minutes of the week in the window's local time, and the window covers the half-open range [start, end). type is "allowed" or "freeze".
• offset is the window's local time minus UTC, in minutes: a UTC-5 zone has offset = -300 and a UTC+2 zone has offset = 120. In UTC the window covers [start - offset, end - offset).
• All times are measured on one UTC timeline in minutes, where minute 0 is the start of the current week and minute 10080 is the start of the next week. Every window occurs once per week on this timeline: at its UTC range, and at that range shifted by every multiple of 10,080 (forwards and backwards). A shifted window may therefore cross a week boundary.
• Freeze wins: a minute inside any freeze occurrence is not deployable, even if an allowed occurrence also covers it. A minute covered by no allowed occurrence is not deployable.
• utc_now is the current UTC minute of the current week. The earliest usable minute is earliest = utc_now + lead_time_minutes. Because the schedule repeats weekly, only the search horizon [earliest, earliest + 10080) is considered.
• A slot is a maximal run of deployable minutes inside the search horizon, reported as [slot_start, slot_end] and meaning the half-open range [slot_start, slot_end). Runs are cut at both ends of the horizon. Deployable minutes that are consecutive on the timeline belong to one slot, even when they come from different windows or cross a week boundary.
• Keep only slots with slot_end - slot_start >= min_continuous_minutes, measured after cutting at the horizon.
• Return the first k kept slots in increasing order of slot_start, fewer if fewer exist, and [] if there are none. Slots never overlap, so this order is unique.

Constraints

• 0 <= utc_now < 10080
• 0 <= lead_time_minutes <= 10^6
• 1 <= min_continuous_minutes <= 10080
• 1 <= k <= 10^4
• 0 <= len(windows) <= 10^4
• 0 <= start < end <= 10080 for every window, in its local time
• type is exactly "allowed" or "freeze"
• -720 <= offset <= 840
• Every returned value lies between 0 and earliest + 10080, which is at most 1,020,159, so all values fit in a 32-bit signed integer.

Examples

Example 1

Input:  utc_now = 0, lead_time_minutes = 0, min_continuous_minutes = 1, k = 10,
        windows = [
          (600, 1200, "allowed", 0),
          (1000, 1080, "freeze", 0),
          (1150, 1500, "allowed", 0),
          (9900, 10080, "allowed", 0),
          (0, 120, "allowed", 0)
        ]
Output: [[0, 120], [600, 1000], [1080, 1500], [9900, 10080]]

The freeze removes [1000, 1080) from the first allowed window. The overlapping allowed ranges [1080, 1200) and [1150, 1500) form one slot. The search horizon is [0, 10080), so [0, 120) and [9900, 10080) are reported as two slots even though the week wraps from one to the other.

Example 2

Input:  utc_now = 10000, lead_time_minutes = 60, min_continuous_minutes = 90, k = 3,
        windows = [
          (0, 240, "allowed", 0),
          (9960, 10080, "allowed", 0),
          (120, 150, "freeze", 0),
          (540, 720, "allowed", 120),
          (3000, 3030, "allowed", 0)
        ]
Output: [[10060, 10200], [10230, 10320], [10500, 10680]]

earliest = 10060, so the horizon is [10060, 20140). The allowed run that starts at 9960 continues across the week boundary into next week's [10080, 10320). It is cut at 10060 and split by next week's freeze [10200, 10230), leaving slots of 140 and 90 minutes. The window with offset = 120 covers UTC [420, 600), which next week is [10500, 10680). Next week's [13080, 13110) lasts only 30 minutes and is dropped. A fourth qualifying slot, [20040, 20140), exists, but k = 3.

Example 3

Input:  utc_now = 50, lead_time_minutes = 0, min_continuous_minutes = 30, k = 5,
        windows = [
          (0, 180, "allowed", 120),
          (30, 60, "freeze", 120)
        ]
Output: [[9960, 9990], [10020, 10130]]

With offset = 120, the allowed window covers UTC [-120, 60), and its next weekly occurrence is [9960, 10140). The freeze covers [9990, 10020) in that occurrence. The horizon is [50, 10130). The run [50, 60) lasts 10 minutes and is dropped, [9960, 9990) lasts exactly 30 minutes and is kept, and [10020, 10140) is cut to [10020, 10130) at the end of the horizon.

Weekly Deployment Slots Across Time Zones

Hints

1. Convert each window to UTC with start - offset and end - offset, then remember it repeats every 10,080 minutes in both directions: ask which weekly copies can reach the horizon [earliest, earliest + 10080).
2. Freeze always wins, and deployable pieces that touch on the timeline form a single slot even when they come from different windows or cross a week boundary.
3. Cut slots to the horizon before checking min_continuous_minutes, and only then take the first k in increasing slot_start order.

Approach

Let W = 10080, lo = utc_now + lead_time_minutes and hi = lo + W, so the search horizon is [lo, hi). Each window becomes the UTC range [a, b) = [start - offset, end - offset), and its weekly occurrences are [a + mW, b + mW) for every integer m. Because b - a <= W and the horizon is exactly W long, at most two occurrences intersect it: the first candidate is m = floor((lo - b) / W) + 1, the smallest m with b + mW > lo, and occurrences are taken while a + mW < hi. Each intersecting occurrence is clipped to [max(a + mW, lo), min(b + mW, hi)) and recorded as +1 at its start and -1 at its end in an allowed counter or a freeze counter. Sweeping the sorted event points maintains how many allowed and how many freeze occurrences cover the segment that begins at the current point; that segment is deployable exactly when the allowed count is positive and the freeze count is zero, which implements 'freeze wins'. A run opens when the state turns deployable and closes when it stops. Occurrences that touch cancel at the shared point, so pieces that are consecutive on the timeline merge into one slot even when they come from different windows or cross a week boundary, while any freeze splits a run. Because every occurrence is clipped before the sweep, runs are automatically cut at both horizon ends before the length filter. Runs are produced in increasing slot_start order, so the result keeps those with slot_end - slot_start >= min_continuous_minutes and stops after k. Edge cases: no windows or only freeze windows give []; a whole-week allowed window yields one slot equal to the whole horizon; every value stays at most 1,020,159, so 32-bit integers suffice in every language.

• Time complexity: O(n log n) where n = len(windows)
• Space complexity: O(n)