Minimum Number of Days to Make m Bouquets — BS on Answer
Advertisement
Problem 315 · Minimum Number of Days to Make m Bouquets
Difficulty: Medium · Pattern: BS on Answer
On day d, flower i blooms if bloomDay[i] <= d. Find min d to make m bouquets of k consecutive flowers.
Solutions
# Python
def minDays(bloomDay, m, k):
if len(bloomDay) < m*k: return -1
def feasible(d):
bouquets = flowers = 0
for b in bloomDay:
if b <= d: flowers += 1
else: flowers = 0
if flowers == k: bouquets += 1; flowers = 0
return bouquets >= m
lo, hi = min(bloomDay), max(bloomDay)
while lo < hi:
mid = (lo+hi)//2
if feasible(mid): hi = mid
else: lo = mid+1
return lo
// Java
public int minDays(int[] bloomDay, int m, int k) {
if ((long)m*k>bloomDay.length) return -1;
int lo=Integer.MAX_VALUE, hi=0;
for (int d:bloomDay) { lo=Math.min(lo,d); hi=Math.max(hi,d); }
while (lo<hi) {
int mid=lo+(hi-lo)/2, bq=0, fl=0;
for (int d:bloomDay) { if(d<=mid){fl++;if(fl==k){bq++;fl=0;}}else fl=0; }
if (bq>=m) hi=mid; else lo=mid+1;
}
return lo;
}
Complexity
- Time: O(n log(max-min))
- Space: O(1)
Advertisement