Make room for a quiet shift

MediumArraysTwo pointersSliding window

A brewery schedules a quiet tasting shift across consecutive minutes. Each entry of noise is the nonnegative number of noisy machine-seconds during that minute. The shift may spend at most budget noisy seconds in total. Return the inclusive zero-based range [start, end] of the longest nonempty shift within budget. If several shifts have the same longest length, return the one starting earliest. If no minute can be included, return [-1, -1]. A shift cannot skip minutes.

Example 1

INPUT[2,0,3,1,0,2], 4OUTPUT[1,4]

Minutes 1 through 4 have total noise 4 and length 4. No length-5 shift fits.

Example 2

INPUT[2,2,2], 4OUTPUT[0,1]

Both length-2 shifts fit. The earlier one starts at minute 0.

Keep in mind

0 <= noise.length <= 20,000
Each noise entry is an integer from 0 to 1,000,000.
0 <= budget <= 20,000,000,000
All sums fit exactly in a JavaScript Number.

/** @param {number[]} noise
 *  @param {number} budget
 *  @returns {number[]} */
function solve(noise, budget) {
  // Return the longest affordable inclusive range.
}

/** @param {number[]} noise
 *  @param {number} budget
 *  @returns {number[]} */
function solve(noise, budget) {
  // Return the longest affordable inclusive range.
}

INPUT[2,0,3,1,0,2], 4

EXPECTED OUTPUT[1,4]

Public samples only. These checks do not award ranked points.

AFTER THE SOLVE

How the solution works.

Walk through a solution, check its time and space costs, and compare it with yours.

Checking your progress…

Make room for a quiet shift

Example 1

Example 2

Keep in mind

How the solution works.

Related problems

Find the busiest tray run

Count the steady pour runs