Longest run of jobs within a budget

MediumAbout 25 minProblem 2 of 3 in Sliding windowDraft

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

  1. longestUnderBudget([4, 2, 1, 3, 5], 6)returns 3Jobs 2, 1 and 3 cost 6.
  2. longestUnderBudget([7, 8], 5)returns 0Every job costs more than the budget.
  3. longestUnderBudget([0, 0, 0], 0)returns 3Free 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open