Minimum-Cost Job Scheduling Across Priced Windows

hardPROPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

Problem Statement

A batch job needs k contiguous compute hours and must finish by a deadline. Electricity/compute price varies by hour. Choose the cheapest contiguous k-hour window within the allowed horizon.

Background

Given hourly prices for hours 0..n-1 and a job length k, find the start hour s (with s + k <= n) minimizing sum(prices[s:s+k]). Return that minimum total cost. Ties pick the earliest start. If k > n, the job cannot be scheduled — return -1.

Your Task

def cheapest_window(prices, k):

Return the minimum total cost, or -1 if infeasible.

Input Format

prices (list of numbers), k (int).

Output Format

A number (min cost) or -1.

Sample

print(cheapest_window([5, 1, 2, 8, 1, 1], 2))

Output:

Example

Input

print(cheapest_window([5, 1, 2, 8, 1, 1], 2))

Output

Reasoning

Feasibility Check: Verify that the job length $k=2$ is less than or equal to the total hours $n=6$ . Since $2 \le 6$ , the job can be scheduled, and we proceed to find the minimum cost.
Initial Window: Calculate the cost of the first contiguous 2-hour window (hours 0 and 1): $5 + 1 = 6$ . This sets the initial minimum cost to 6.
Sliding Window Updates: Shift the window one hour at a time to evaluate all possible start positions:
- Start at hour 1: Add price at hour 2 ( $2$ ) and subtract price at hour 0 ( $5$ ). New cost: $6 + 2 - 5 = 3$ . Update minimum to 3.
- Start at hour 2: Add price at hour 3 ( $8$ ) and subtract price at hour 1 ( $1$ ). New cost: $3 + 8 - 1 = 10$ . Minimum remains 3.
- Start at hour 3: Add price at hour 4 ( $1$ ) and subtract price at hour 2 ( $2$ ). New cost: $10 + 1 - 2 = 9$ . Minimum remains 3.
- Start at hour 4: Add price at hour 5 ( $1$ ) and subtract price at hour 3 ( $8$ ). New cost: $9 + 1 - 8 = 2$ . Update minimum to 2.
Final Output: The lowest cost found among all valid windows is 2.

Constraints

Window is contiguous of length k, s + k <= n.
Minimize the window sum; ties -> earliest start.
k > n -> return -1; use a sliding-window sum for O(n).

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Deduplicate Retried Pipeline Runs by Idempotency Keymedium Retry with Capped Exponential Backoff and Jitter Capmedium Critical Path Length of a Pipeline DAGmedium Pipeline Stages Ready to Runeasy

Concept primerPREVIEW

1. Background Knowledge

This problem is a classic application of the sliding window technique, a fundamental pattern in array and string processing. Instead of recalculating a sum from scratch for every possible subarray of length $k$ , you maintain a running total and update it incrementally as the window shifts one position to the right. This transforms a quadratic-time brute force into a linear-time solution.

In the context of ML infrastructure, this models cost-aware scheduling. Compute resources often have time-varying prices (e.g., spot instances, off-peak electricity). A batch job requiring $k$ contiguous hours must be placed in the cheapest available window to minimize operational expenditure while meeting the deadline constraint (implicitly handled by the array bounds).

The mathematical core is finding the minimum of a sequence of sliding sums. If $S_i = \sum_{j=i}^{i+k-1} \text{prices}[j]$ , we seek $\min(S_0, S_1, \dots, S_{n-k})$ . The key insight is that consecutive window sums differ only by the element leaving the window and the element entering it: $S_{i+1} = S_i - \text{prices}[i] + \text{prices}[i+k]$ .

2. Algorithm Approach

Use a fixed-size sliding window with a running sum:

Initialize: Compute the sum of the first $k$ elements.
Slide: For each subsequent position, subtract the leftmost element of the previous window and add the new rightmost element.
Track Minimum: Keep a variable for the minimum cost seen so far. Update it only if the current window sum is strictly smaller (to preserve the earliest start on ties).
Edge Case: If $k > n$ or $k \leq 0$ , return $-1$ immediately.

This approach avoids nested loops and leverages the overlapping structure of contiguous subarrays.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.