# 1482. Minimum Number of Days to Make m Bouquets
#### Difficulty: Medium
link: https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/

### 1. Binary Search
#### $O(n * log\ (max(bloomDay) - min(bloomDay)))$ runtime, $O(1)$ space

在一個日期範圍內不斷猜測，找出最小能滿足做出m個花束條件的值。使用binary search較有效率，套用模板！

邊界範圍，`min(bloomDay)`至少一朵花和`max(bloomDay)`全部開花的日期。

##### python

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if len(bloomDay) < m * k:
            return -1
        
        def enough_bouquets(days):
            flow, bouq = 0, 0
            for b in bloomDay:
                flow = flow + 1 if b <= days else 0
                
                if flow >= k:
                    bouq += 1
                    flow = 0
                
                # early stop
                if bouq >= m:
                    return True
            
            return False
        
        left, right = min(bloomDay), max(bloomDay)
        
        while left < right:
            mid = left + (right - left) // 2
            if enough_bouquets(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

###### tags: `leetcode`