# LC1482 - Minimum Number of Days to Make m Bouquets
## 线性关系 二分查找猜答案

class Solution {
    /*
    x: the number of days
    f(x): if the number of days is x, it can make f(x) bouquets
    */
    public int minDays(int[] bloomDay, int m, int k) {
        // sanity check
        // ...
        int result = -1;
        int length = bloomDay.length;
        
        if (m * k > length) {
            return result;
        }
        
        int minDay = 1000000000 + 1;
        int maxDay = 0;
        for (int day : bloomDay) {
            minDay = Math.min(minDay, day);
            maxDay = Math.max(maxDay, day);
        }
        
        while (minDay + 1 < maxDay) {
            int midDay = minDay + (maxDay - minDay) / 2;
            if (canMakeBouquetsBy(midDay, k, m, bloomDay)) {
                maxDay = midDay;
            } else {
                minDay = midDay;
            }
        }
        
        // minimum
        if (canMakeBouquetsBy(minDay, k, m, bloomDay)) {
            return minDay;
        }
        if (canMakeBouquetsBy(maxDay, k, m, bloomDay)) {
            return maxDay;
        }
        return -1;
    }
    
    // proportional function
    private boolean canMakeBouquetsBy(int targetDay, int targetNumFlowers, int targetNumBouquets, int[] bloomDay) {
        int length = bloomDay.length;
        int numFlowers = 0;
        int numBouquets = 0;
        
        for (int i = 0; i < length; i++) {
            if (targetDay >= bloomDay[i]) {
                numFlowers++;
            } else {
                numFlowers = 0;
            }
            
            if (numFlowers == targetNumFlowers) {
                numBouquets++;
                numFlowers = 0;
            }
            
            if (numBouquets >= targetNumBouquets) {
                return true;
            }
        }
        
        return false;
    }
}