動機

  • 只要有某個範圍是連續遞增就可以用bsearch!!
  • 寫bsearch就是考慮那邊要丟掉就設成a = mid+1

Problem

Given an integer array bloomDay, an integer m and an integer k.

We need 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 = 1Output: 3Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't 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 = 2Output: -1Explanation: 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 = 3Output: 12Explanation: We need 2 bouquets each should have 3 flowers.Here's 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.

Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1Output: 1000000000Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2Output: 9

 

Constraints:

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

Sol

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m*k > len(bloomDay):
            return -1        

        def count(day):
            ret = 0
            i = 0
            while i < len(bloomDay):
                if bloomDay[i] <= day:
                    j = i+1
                    while j < len(bloomDay) and bloomDay[j] <= day:
                        j += 1
                    ret += (j-i)//k
                    i = j
                else:
                    i += 1
            return ret 

        a,b = min(bloomDay), max(bloomDay)
        while a<b:
            mid = (a+b)//2
            #print(a,mid,b,count(mid))
            if count(mid) < m:
                a = mid+1
            else:
                b = mid
        return a