How should I practice Minimize the Longest Hike Between Rest Stops?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Pinterest onsite interview problems in FastPrep.

Is Minimize the Longest Hike Between Rest Stops associated with Pinterest?

FastPrep tags this as a Pinterest onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Minimize the Longest Hike Between Rest Stops

Learn this problem

● Medium

PinterestFULLTIMEONSITE INTERVIEW

Problem statement

You are given an array segments, where segments[i] is the positive hiking time of the ith consecutive segment of one route, and an integer restStops.

Place every rest stop between two adjacent segments. Using exactly restStops rest stops divides the route into exactly restStops + 1 nonempty continuous hiking groups. The duration of a group is the sum of its segment times.

Return the minimum possible value of the maximum group duration. You only need to return this minimum duration; you do not need to reconstruct a placement.

Function

minimizeLongestHike(segments: int[], restStops: int) → long

Examples

Example 1

segments = [7,2,5,10,8]restStops = 1return = 18

Place the rest stop after the third segment. The two group durations are 14 and 18. Every other placement has a maximum duration of at least 18.

Example 2

segments = [4,2,7,3,6]restStops = 2return = 9

Use groups [4,2], [7], and [3,6], whose durations are 6, 7, and 9. A maximum below 9 cannot fit these segments into three groups.

Example 3

segments = [6,3,8]restStops = 2return = 8

Every segment forms its own group, so the longest continuous hike is the longest individual segment.

Constraints

1 <= segments.length <= 100000.
1 <= segments[i] <= 10^9.
0 <= restStops < segments.length.
The sum of all segment times fits in a signed 64-bit integer.