Minimum-Cost Job Scheduling Across Priced Windows
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:
2
Example:
print(cheapest_window([5, 1, 2, 8, 1, 1], 2))
2
- Feasibility Check: Verify that the job length k=2 is less than or equal to the total hours n=6. Since 2≤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).
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 Si=∑j=ii+k−1prices[j], we seek min(S0,S1,…,Sn−k). The key insight is that consecutive window sums differ only by the element leaving the window and the element entering it: Si+1=Si−prices[i]+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≤0, return −1 immediately.
This approach avoids nested loops and leverages the overlapping structure of contiguous subarrays.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.