Find Weekly Deployment Windows Across Time Zones

Problem Statement

Global engineering teams operate across different time zones with specific deployment policies. Some policies define when deployments are permitted (ALLOW), while others enforce quiet periods or code freezes (FREEZE). All policies recur weekly on local schedules.

You are tasked with finding the first k non-overlapping deployment windows of length duration minutes that satisfy all policies.

A repeating UTC week consists of 10,080 minutes (7 * 24 * 60), indexed from 0 (Sunday 00:00 UTC) to 10079 (Saturday 23:59 UTC).

Each rule is defined with:

• rule_type: "ALLOW" or "FREEZE"
• day: Day of week (0 = Sunday, 1 = Monday, ..., 6 = Saturday)
• start_minute: Minute within the day (0 to 1439, inclusive)
• end_minute: Minute within the day (1 to 1440, exclusive boundary, where 1440 is midnight of the next day)
• tz_offset: Time zone offset from UTC in minutes (Local Time = UTC + tz_offset)

A UTC minute m (0 <= m < 10080) is considered deployable if and only if:

1. It falls within at least one active ALLOW rule (after translating the rule to UTC).
2. It does not fall within any active FREEZE rule (after translating the rule to UTC).

A deployment window of size duration starting at absolute UTC minute T is valid if every minute in [T, T + duration) is deployable (i.e., t % 10080 is deployable for all t in the window).

Find and return the start times of the first k valid, non-overlapping deployment windows. Search strictly within the range [current_utc_minute + lead_time, current_utc_minute + 3 * 10080).

Function Signature

def find_deployment_windows(
    rules: list[dict],
    duration: int,
    lead_time: int,
    current_utc_minute: int,
    k: int
) -> list[int]:
    pass

Input & Output Format

• rules: List of dicts, each with keys 'type' ("ALLOW" | "FREEZE"), 'day' (int), 'start_minute' (int), 'end_minute' (int), and 'tz_offset' (int).
• Return a list of up to k integers representing the starting absolute UTC minutes (from week 0, minute 0) in ascending order. If fewer than k windows exist within the 3-week search horizon, return all available windows.

Constraints

• 1 <= duration <= 1440
• 0 <= lead_time <= 10080
• 0 <= current_utc_minute < 10080
• 1 <= k <= 50
• 1 <= len(rules) <= 200
• -720 <= tz_offset <= 840

Examples

Example 1

rules = [
    {"type": "ALLOW", "day": 0, "start_minute": 120, "end_minute": 300, "tz_offset": 0},
    {"type": "FREEZE", "day": 0, "start_minute": 180, "end_minute": 200, "tz_offset": 0}
]
duration = 60
lead_time = 10
current_utc_minute = 100
k = 2

# Output: [200, 10280]

Explanation: Allowed UTC range is [120, 180) and [200, 300). Earliest search start is 100 + 10 = 110. Window [130, 190) overlaps the freeze [180, 200). The first valid 60-minute window is [200, 260). The next non-overlapping window on week 0 would need to start at >= 260, but the allowed window ends at 300 (insufficient length). The second window occurs in week 1 at minute 10080 + 200 = 10280.