FastPrep
Problem · Dynamic Programming

Efficient Trek

Learn this problem
● HardLinkedIn logoLinkedInINTERNOA

Problem statement

A hiker is planning a multi-day trek through the mountains. There are trails, each with a certain length, given as a list, trails, that need to be hiked in the order in the list. The hiker wants to achieve a new world record by completing the trek in record number of days. Each day, the hiker will cover at least one trail and must minimize the sum of the lengths of the longest trail hiked each day. Find this minimum sum.

Example: There are n = 6 trails with lengths trails= [10, 5, 9, 3, 8, 15] and days = 2. One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 + 15 = 25. Return 25.

Function

efficientTrek(trails: int[], days: int) → int

Complete the function efficientTrek in the editor.

efficientTrek has the following parameters:

  1. int trails[]: an array of integers denoting the order and length of the trails.
  2. int days: the number of days to cover all the trails.

Returns

int: the minimum sum of the longest trails on each day

Examples

Example 1

trails = [10, 5, 9, 3, 8, 15]days = 2return = 25
One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 + 15 = 25. Return 25.

Constraints

  • 1 ≤ n ≤ 300
  • 1 ≤ days ≤ n ≤ 300
  • 1 ≤ trails[i] ≤ 10^5

More LinkedIn problems

drafts saved locally
public int efficientTrek(int[] trails, int days) {
  // write your code here
}
trails[10, 5, 9, 3, 8, 15]
days2
expected25
checking account