https://binarysearch.com/problems/Skydivers
You are given a list of integers nums where each value represents a group of people looking to skydive together. You are also given k representing the number of days the skydiving facility is open for.
Return the minimum capacity of the plane you need to be able to fulfill all requests in k days. Note that requests should be fulfilled in the order they were given and a plane can only have one flight per day.
Constraints
-
n ≤ 10,000wherenis the length ofnums.
Example 1
Input
nums = [13, 17, 30, 15, 17]
k = 3
Output
32
Explanation
A 32 person airplane can group the requests by [13, 17], [30], [15, 17].
Intuition
Binary Search
- left is the maximum group of people
- right is the whole people of groups
- need to calculate minimal capacity, so it needs binary search left boundary
Implementation
Binary Search Left Boundary Template
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left] == target ? left : -1;
}
}
Time Complexity
O(n*log*n): every time you change capacity, you need to loop the nums again
Space Complexity
O(1): just few varieties to store left, right and capacity days
import java.util.*;
class Solution {
public int solve(int[] nums, int k) {
int max = 0, sum = 0;
for (int num : nums) {
max = max > num ? max : num;
sum += num;
}
int left = max, right = sum;
while (left < right) {
int capacity = (left + right) / 2;
int day = 1, peopleOnTheDay = 0;
for (int groupOfPeople : nums) {
if (peopleOnTheDay + groupOfPeople <= capacity) {
peopleOnTheDay += groupOfPeople;
} else {
peopleOnTheDay = groupOfPeople;
day++;
}
}
if (day > k) {
left = capacity + 1;
} else {
right = capacity;
}
}
return left;
}
}
Top comments (0)