Implement a scheduler that fits deployments into allowed deployment windows

In an online assessment you implement a deployment window scheduler. Deployments may run only inside allowed deployment windows, and the scheduler decides when each requested deployment runs, or reports that a request cannot be placed. The report gives only the name of the task and notes that versions of it differ in the output format they expect, so confirm the input format, the placement rules and the output format before you write code. The assessment is graded by automated test cases. Because the report does not state the rules, take this baseline as an assumption and adjust it to whatever the prompt specifies: - The allowed windows are time intervals, given in any order. - Each deployment request has an identifier, the earliest time it may start and a duration. - A deployment runs without interruption inside allowed time, and for every request the scheduler returns when it runs or that it cannot run. Implement the scheduler and state the rule it uses to choose each start time. ```hint Clean up the windows first Think about what goes wrong if windows arrive unsorted, overlap or touch each other, and which form makes "the first window that can still hold this deployment" cheap to find. ``` ```hint Boundaries are where tests fail Decide whether a deployment that ends exactly when a window closes fits, and whether it may continue from one window straight into an adjacent one. ``` ```hint Booked time is no longer free If deployments may not overlap, ask how you find the earliest free gap inside a window after earlier deployments have taken part of it. ``` ### Clarifying Questions - Are windows absolute start and end timestamps, or recurring slots such as daily or weekly hours, and in which time zone? - Is a window's end inclusive or exclusive, and may a deployment span two windows that overlap or touch? - May two deployments run at the same time, or must they run one after another? - Are requests placed in the order given, sorted by earliest start, or by some priority, and is the output listed in input order? - What should the scheduler return for a request that fits in no window: a marker, an error, or nothing at all? - What exact output is expected for each request: a start time, a start and an end, the window used, or a formatted string? ### What a Strong Answer Covers - Window format, boundary semantics, overlap rule and output format confirmed before coding - Window normalization: ordering, merging or rejecting overlaps, and discarding empty or inverted windows - A deterministic placement rule and request order, stated explicitly - An efficient search for the next window or free gap that can hold a deployment, with its complexity - Edge cases: requests longer than every window, earliest starts inside or after the last window, zero durations, ties - Scheduling logic kept separate from output formatting, with tests that pin each boundary case ### Follow-up Questions - Windows recur every week and requests may be far in the future. How do you find the next suitable window without listing every occurrence? - Up to k deployments may run at the same time. How does placement change? - A scheduled deployment is cancelled. How do you free its time, and should later deployments move earlier? - Requests carry priorities, and a high-priority request may displace a lower-priority one. Which rules keep the schedule predictable?