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.