Minimum Time to Transport All Individuals - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
3594. Minimum Time to Transport All Individuals
Hard
50 Points
Array
Dynamic Programming
Bit Manipulation
Graph
Heap (Priority Queue)
Shortest Path
Bitmask
You are given n individuals at a base camp who need to cross a river to reach a destination using a single boat. The boat can carry at most k people at a time. The trip is affected by environmental conditions that vary cyclically over m stages.
Each stage j has a speed multiplier mul[j]:
Each individual i has a rowing strength represented by time[i], the time (in minutes) it takes them to cross alone in neutral conditions.
Rules:
Return the minimum total time required to transport all individuals. If it is not possible to transport all individuals to the destination, return -1.
Examples
Example 1
Input: n = 1, k = 1, m = 2, time = [5], mul = [1.0,1.3]
Output: 5.00000
Explanation:
Example 2
Input: n = 3, k = 2, m = 3, time = [2,5,8], mul = [1.0,1.5,0.75]
Output: 14.50000
Explanation:
The optimal strategy is:
Example 3
Input: n = 2, k = 1, m = 2, time = [10,10], mul = [2.0,2.0]
Output: -1.00000
Explanation:
Constraints
1 <= n == time.length <= 12
1 <= k <= 5
1 <= m <= 5
1 <= time[i] <= 100
m == mul.length
0.5 <= mul[i] <= 2.0
3594. Minimum Time to Transport All Individuals
Hard
50 Points
Array
Dynamic Programming
Bit Manipulation
Graph
Heap (Priority Queue)
Shortest Path
Bitmask
You are given n individuals at a base camp who need to cross a river to reach a destination using a single boat. The boat can carry at most k people at a time. The trip is affected by environmental conditions that vary cyclically over m stages.
Each stage j has a speed multiplier mul[j]:
Each individual i has a rowing strength represented by time[i], the time (in minutes) it takes them to cross alone in neutral conditions.
Rules:
Return the minimum total time required to transport all individuals. If it is not possible to transport all individuals to the destination, return -1.
Examples
Example 1
Input: n = 1, k = 1, m = 2, time = [5], mul = [1.0,1.3]
Output: 5.00000
Explanation:
Example 2
Input: n = 3, k = 2, m = 3, time = [2,5,8], mul = [1.0,1.5,0.75]
Output: 14.50000
Explanation:
The optimal strategy is:
Example 3
Input: n = 2, k = 1, m = 2, time = [10,10], mul = [2.0,2.0]
Output: -1.00000
Explanation: