1482.minimum-number-of-days-to-make-m-bouquets.md

1482. Minimum Number of Days to Make m Bouquets

Binary Search

隨著時間的推移，花越開越多，越來越密集，越可以用的機率越高。早期的時候，花開得很零散，很難找到連續 k 朵形成一個花束。天數越後面，越可能找到連續的花朵。這是一個單調遞增的特性，時間越早越不容易達成目標、時間越往後越容易達成目標。這樣特性就很適合用二分搜值。

For this problem, the earliest day to wait to make at least one bouqest is the min(bloomDay), the fastest flower to bloom (regardless of actual m or k), no flower is bloomed before that. And the worst case is that we have to wait for the slowest flower to bloom, that is max(bloomDay).

flowers = [1,4,2,3] 
   1,4,2,3
d1 O X X X
d2 O X O X
d3 O X O O
d4 O O O O

m = 1, k = 1: minimum wait for 1 day to make 1 bouquet
m = 4, k = 1: minimum wait for 4 days to make all 4 bouquets
m = 1, k = 4: minimum wait for 4 days to make 1 bouquet

And if we can make it when waiting for d days, then we can also make it when waiting for d+1, d+2, ..., max(bloomDay) days. If we can't make it when waiting for d days, then we can't make it when waiting for d-1, d-2, ..., min(bloomDay) days. This is monotonicity, so we can use binary search to find the answer. NOTE: Ensure to check if the left is out of bound (left in min..max).

// (m = 1, k = 3) or (m = 3, k = 1)
days    [1, 5, 3]   can make?
1       [O, X, X]   X
2       [O, X, X]   X
3       [O, X, O]   X
4       [O, X, O]   X
5       [O, O, O]   O <- answer
6       [O, O, O]   O
...

// Another example:
days    [7, 7, 9]
1       [X, X, X]   X
2       [X, X, X]   X
...
7       [O, O, X]   X
8       [O, O, X]   X
9       [O, O, O]   O <- answer
10      [O, O, O]   O
...

fun minDays(bloomDay: IntArray, m: Int, k: Int): Int {
    val n = bloomDay.size
    if (n < m * k) return -1

    var min = Int.MAX_VALUE
    var max = Int.MIN_VALUE
    for (b in bloomDay) {
        min = minOf(min, b)
        max = maxOf(max, b)
    }

    var left = min
    var right = max
    while (left <= right) {
        val middle = left + (right - left) / 2

        if (canMake(bloomDay, middle, m, k)) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    // Remember to check if left is out of bound. That is the case
    // [X, X, X]
    //           ^ left
    return if (left > max) -1 else left
}

private fun canMake(bloomDay: IntArray, day: Int, m: Int, k: Int): Boolean {
    var bouquets = 0
    var flowers = 0
    for (i in 0 until bloomDay.size) {
        if (bloomDay[i] <= day) {
            flowers++
        } else {
            flowers = 0
        }

        if (flowers == k) {
            bouquets++
            flowers = 0
        }
        // Early return here (optional)
        if (m <= bouquets) return true
    }
    return m <= bouquets
}

// Or equivalently, straightforward implementation, inner loop to find the next `k` flowers.
private fun canMake(bloomDay: IntArray, day: Int, m: Int, k: Int): Boolean {
    var i = 0
    var bouquets = 0 // If we can make `m` bouquets
    while (i < bloomDay.size) {
        val canBloom = bloomDay[i] <= day
        if (!canBloom) {
            i++
            continue
        }

        var j = i
        var flowers = 0 // If we can use `k` flowers to make a bouquet
        // If we can bloom, and not enough flowers to make the current bouquet
        while (j < bloomDay.size && flowers < k && bloomDay[j] <= day) {
            flowers++
            j++
        }
        if (k <= flowers) {
            bouquets++
        }
        i = j
    }
    return m <= bouquets
}

• Time Complexity: O(log(max(days) - min(days)) * n)
• Space Complexity: O(1)