Ctrl K

The Gentlest Every-Other-Day Plan

Medium
An athlete is planning workouts. The array loads gives the strain of the workout available on each of a run of consecutive days. Working out on two days in a row is not allowed, and there must be at least count workouts in total. The *peak* of a plan is the largest load among the chosen days. Return the smallest possible peak over all plans with at least count days in which no two chosen days are consecutive. It is guaranteed that count non-consecutive days can be chosen.
Example 1
loads=[6, 2, 8, 3, 7], count=2 → 3

Days 1 and 3 (loads 2 and 3) are not adjacent, since day 2 lies between them, so the peak can be just 3.

Example 2
loads=[4, 1, 5], count=2 → 5

The only two non-adjacent days out of three are 0 and 2, so the peak is max(4, 5) = 5.

Example 3
loads=[9, 3, 3, 9, 1], count=3 → 9
Constraints
  • 1 ≤ len(loads) ≤ 10⁵
  • 1 ≤ loads[i] ≤ 10⁹
  • 1 ≤ count ≤ (len(loads) + 1) / 2
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsFind in a Shifted Sorted Array MediumFirst and Last Copy MediumFind in a Row-Chained Grid MediumFind in a Shifted Array With Repeats MediumMinimum of a Shifted List Medium
loading Python…
Input
loads=[6, 2, 8, 3, 7], count=2
Expected
3

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.