Minimum Number of Days to Make m Bouquets 1482

tags: leetcode,binarySearch,medium

ref: https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/

You are given an integer array bloomDay, an integer m and an integer k.

You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.

Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here is the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Constraints:
bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

1. binary search: 觀察條件狀況為遞增或遞減=>
   當a 天時有n 朵花可用, a+1天必定有>=n朵花可用 (連續遞增條件)=>
   邊界為第一天與 bloomDay最大值(10^9)

2. looping過程中start 會一直推進,當start跟end差一時會檢驗的是start,收斂到 start==end為夾擠結果 即為解

	public int minDays(int[] bloomDay, int m, int k) {

		if (m * k > bloomDay.length)
			return -1;

		int lower = 1;

		int upper = 1_000_000_000;

		while (lower < upper) {

			int med = lower + (upper - lower) / 2;  //避免lower+upper 超過int邊界

			int bouq_num = 0;

			t1: for (int i = 0; i < bloomDay.length; i++) {

				int j = i; 

				t2: while (j < bloomDay.length && med >= bloomDay[j]) {   // &&避免 indexoutofboundary   
                    //直接計算可否成花束
					if (j - i + 1 >= k) {
						bouq_num++;
						break t2;
					}
					j++;
				}
				i = j;

				if (bouq_num >= m) { //提早符合條件時可結束, 代表med可下修
					break t1;
				}

			}

			if (bouq_num >= m) {
				upper = med;    // 不可設定成med-1 , 因med 計算為 (upper+lower)/2, 設定為med-1 會損失檢驗med的機會
			} else {
				lower = med + 1; // 因為med 條件不會達成題目條件 故可設定為med+1
			}

		}

		return lower;

	}