Longest run of jobs within a budget
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A batch worker processes jobs in a fixed order. costs[i] is how many credits job i uses; no job uses a negative amount.
You may run any contiguous series of jobs, as long as their total cost is at most budget. Return the length of the longest such series. If no single job fits, return 0.
- 0 ≤ costs.length ≤ 200,000
- 0 ≤ costs[i] ≤ 10,000
- 0 ≤ budget ≤ 10⁹
Examples
longestUnderBudget([4, 2, 1, 3, 5], 6)returns3Jobs 2, 1 and 3 cost 6.longestUnderBudget([7, 8], 5)returns0Every job costs more than the budget.longestUnderBudget([0, 0, 0], 0)returns3Free jobs always fit.
Hints
Hint 1 of 2
Keep the running total of the window. When adding the next job pushes it over budget, what can you do instead of starting again?
Hint 2 of 2
Drop jobs from the left until the total fits again. Costs are never negative, so dropping a job never raises the total.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Fix the right end and ask for the furthest-left start whose total still fits. As the right end moves on, that start can only move right too: a total that was over budget only grows when you add a job, because no job costs less than nothing.
So keep a running total. Add costs[right], then take jobs off the left while the total is over budget. The window that remains is the longest one ending at right.
A common mistake is to throw the whole window away and start again at the job that broke the budget. In [4, 2, 1, 3, 5] with a budget of 6, adding the 1 makes 7; restarting at the 1 misses [2, 1, 3], which fits once only the 4 is dropped.
If costs could be negative, dropping a job could raise the total and the window would no longer shrink in one direction. That version needs prefix sums and a sorted structure instead.
function longestUnderBudget(costs, budget) {
let left = 0, total = 0, best = 0;
for (let right = 0; right < costs.length; right++) {
total += costs[right];
while (total > budget) total -= costs[left++];
best = Math.max(best, right - left + 1);
}
return best;
}Complexity. O(n) time: each job is added once and removed at most once. O(1) extra space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.