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 ```python 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** ```text 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** ```text 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** ```text 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.