← Static tasks

1482. Minimum Number of Days to Make m Bouquets

leetcode medium

#array#csharp#leetcode#medium#search

Task

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.

Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -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.

C# solution

matched/original
public class Solution {
    private int GetNumOfBouquets(int[] bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        foreach (int day in bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }
    public int MinDays(int[] bloomDay, int m, int k) {
        if (bloomDay.Length < m * k) return -1;
        int start = 0, end = bloomDay.Max();
        int minDays = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (GetNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int GetNumOfBouquets(vector<int>& bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        foreach (int day in bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }
    public int MinDays(vector<int>& bloomDay, int m, int k) {
        if (bloomDay.size() < m * k) return -1;
        int start = 0, end = bloomDay.Max();
        int minDays = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (GetNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
}

Java solution

matched/original
class Solution {

    private int getNumOfBouquets(int[] bloomDay, int mid, int k) {
        int numOfBouquets = 0;
        int count = 0;

        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= mid) {
                count++;
            } else {
                count = 0;
            }

            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }

        return numOfBouquets;
    }

    public int minDays(int[] bloomDay, int m, int k) {
        int start = 0;
        int end = 0;
        for (int day : bloomDay) {
            end = Math.max(end, day);
        }

        int minDays = -1;
        while (start <= end) {
            int mid = (start + end) / 2;

            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return minDays;
    }
}

Python solution

matched/original
class Solution:
    def getNumOfBouquets(self, bloomDay, mid, k):
        numOfBouquets = 0
        count = 0
        for day in bloomDay:
            if day <= mid:
                count += 1
            else:
                count = 0
            if count == k:
                numOfBouquets += 1
                count = 0
        return numOfBouquets

    def minDays(self, bloomDay, m, k):
        if len(bloomDay) < m * k:
            return -1
        start, end = 0, max(bloomDay)
        minDays = -1
        while start <= end:
            mid = (start + end) // 2
            if self.getNumOfBouquets(bloomDay, mid, k) >= m:
                minDays = mid
                end = mid - 1
            else:
                start = mid + 1
        return minDays

Go solution

matched/original
func getNumOfBouquets(bloomDay []int, mid int, k int) int {
    numOfBouquets := 0
    count := 0
    for _, day := range bloomDay {
        if day <= mid {
            count++
        } else {
            count = 0
        }
        if count == k {
            numOfBouquets++
            count = 0
        }
    }
    return numOfBouquets
}

func minDays(bloomDay []int, m int, k int) int {
    if len(bloomDay) < m*k {
        return -1
    }
    start, end := 0, 0
    for _, day := range bloomDay {
        if day > end {
            end = day
        }
    }
    minDays := -1
    for start <= end {
        mid := (start + end) / 2
        if getNumOfBouquets(bloomDay, mid, k) >= m {
            minDays = mid
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return minDays
}

Explanation

Algorithm

Инициализация:

Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.

Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

Поиск минимального числа дней:

Выполняйте бинарный поиск, пока start меньше или равен end:

- рассчитайте mid как среднее значение между start и end.

- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.