LeetCode 1482: Minimum Number of Days to Make m Bouquets
Problem Description
Explanation:
To solve this problem, we can use binary search to find the minimum number of days needed to make m bouquets. We can set the search range from the minimum bloom day to the maximum bloom day. For each mid value in the search range, we check if we can make m bouquets using k adjacent flowers with blooming days less than or equal to the mid value.
We can iterate through the bloomDay array, and whenever we find k adjacent flowers with blooming days less than or equal to the mid value, we increment a counter for the number of bouquets. If the counter reaches m, it means we can make m bouquets within mid days. We continue the binary search to find the minimum number of days.
:
Solutions
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
if (m * k > bloomDay.length) {
return -1;
}
int left = 1, right = (int)1e9;
while (left < right) {
int mid = left + (right - left) / 2;
if (canMakeBouquets(bloomDay, m, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canMakeBouquets(int[] bloomDay, int m, int k, int days) {
int bouquets = 0;
int flowers = 0;
for (int i = 0; i < bloomDay.length; i++) {
if (bloomDay[i] <= days) {
flowers++;
if (flowers == k) {
bouquets++;
flowers = 0;
}
} else {
flowers = 0;
}
}
return bouquets >= m;
}
}Loading editor...