---
# System prepended metadata

title: 'LeetCode #1482 [Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)'
tags: [Binary Search, LeetCode, Medium]

---

###### tags: `LeetCode` `Binary Search` `Medium`
# LeetCode #1482 [Minimum Number of Days to Make m Bouquets](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/)
### (Medium)

給你一個整數數組 bloomDay，以及兩個整數 m 和 k 。

現需要製作 m 束花。製作花束時，需要使用花園中 相鄰的 k 朵花 。

花園中有 n 朵花，第 i 朵花會在 bloomDay[i] 時盛開，恰好可以用於一束花中。

請你返回從花園中摘 m 束花需要等待的最少的天數。如果不能摘到 m 束花則返回 -1。

---
若m*n大於bloomDays.size(), 則直接回傳-1。

左值為最早開花時間, 右值為最晚開花時間。

在左值與右值中使用二元搜尋, 並使用for迴圈遍歷整個數組, 當遇到該天數還沒開花的位置時, 直接將記數歸零(因為不連續), 而若該位置開花則記數+1。

當記數值達到k時, 可製成一束花, 此時將花束數量+1, 記數歸零。

for迴圈結束後, 判斷花束數是否滿足m, 若滿足則將右值設為中值, 反之將左值設為中值加一。

最後, 若左值大於等於(其實是等於)數組中最大值+1, 則回傳-1, 反之回傳左值。

---
```
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(m*k>bloomDay.size())return -1;
        int l=INT_MAX, r=0;
        for(auto b:bloomDay){
            l=min(l,b);
            r=max(r,b);
        }
        int max=r;
        while(l<r){
            int mid=(r+l)/2;
            int nob=0, cnt=0;
            for(auto b:bloomDay){
                if(b>mid){cnt=0;continue;}
                else cnt++;
                if(cnt>=k){
                    nob++;
                    cnt=0;
                }
            }
            if(nob<m)l=mid+1;
            else r=mid;
        }
        if(l>=max+1)return -1;
        return l;
    }
};
```