1482. Minimum Number of Days to Make m Bouquets

LeetCode medium original: C# #array #csharp #leetcode #medium #search

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

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

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

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

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

Example:

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
}

Algorithm

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

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

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

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

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

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

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

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.