Minimum Number of Days to Make m Bouquets

class Solution {
public:
    int calculateBouquets(vector<int>& bloomDays, int currentDay, int flowersPerBouquet) {
        int bouquetCount = 0;
        int flowerStreak = 0;
        
        for (int day : bloomDays) {
            if (day <= currentDay) {
                flowerStreak++;
            } else {
                flowerStreak = 0;
            }

            if (flowerStreak == flowersPerBouquet) {
                bouquetCount++;
                flowerStreak = 0;
            }
        }

        return bouquetCount;
    }

    int findMinimumDays(vector<int>& bloomDays, int requiredBouquets, int flowersPerBouquet) {
        int firstDay = 0;
        int lastDayMaximum = 0;
        
        for (int day : bloomDays) {
            lastDayMaximum = max(lastDayMaximum, day);
        }

        int result = -1;
        while (firstDay <= lastDayMaximum) {
            int middleDay = (firstDay + lastDayMaximum) / 2;

            if (calculateBouquets(bloomDays, middleDay, flowersPerBouquet) >= requiredBouquets) {
                result = middleDay;
                lastDayMaximum = middleDay - 1;
            } else {
                firstDay = middleDay + 1;
            }
        }

        return result;
    }
};

The provided C++ code defines a class named Solution that includes two primary functions aimed at solving the problem of determining the minimum number of days required to form a certain number of bouquets from flowers, which bloom on specific days.

• Function calculateBouquets: This function accepts a vector of integers bloomDays, an integer currentDay, and another integer flowersPerBouquet. It counts how many bouquets can be formed by the currentDay where each bouquet requires a consecutive sequence of flowersPerBouquet blooms. A loop iterates through bloomDays to count blooms by currentDay, resetting the count when it reaches the number required for a bouquet and continuing until the end of the vector. It returns the total number of bouquets that can be formed by currentDay.

• Function findMinimumDays: This function accepts the bloomDays vector, an integer requiredBouquets, and an integer flowersPerBouquet. Using a binary search approach, it determines the earliest day by which it's possible to make the required number of bouquets. It initializes firstDay as 0 and lastDayMaximum by finding the maximum day a flower blooms within the bloomDays. Within a while loop, the binary search narrows down the potential days by checking, with the calculateBouquets function, if the middle day can result in the required number of bouquets. Depending on the result, it adjusts the search range either narrowing down to earlier days or later days until it successfully finds the minimum day.

The code effectively leverages binary search, minimizing the number of days checked and optimizing performance, particularly useful considering variable bloom days and large data sets. This solution is highly efficient for determining the minimum number of days needed to gather sufficient blooms for the required bouquets, given bouquets are made of flowers blooming consecutively.

class Solution {

    private int checkBouquets(int[] days, int maxDay, int flowers) {
        int bouquets = 0;
        int blooms = 0;
        for (int day : days) {
            if (day <= maxDay) {
                blooms++;
            } else {
                blooms = 0;
            }

            if (blooms == flowers) {
                bouquets++;
                blooms = 0;
            }
        }
        return bouquets;
    }

    public int minDays(int[] days, int m, int k) {
        int low = 0;
        int high = 0;
        for (int day : days) {
            high = Math.max(high, day);
        }

        int minRequiredDays = -1;
        while (low <= high) {
            int mid = (low + high) / 2;

            if (checkBouquets(days, mid, k) >= m) {
                minRequiredDays = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return minRequiredDays;
    }
}

This Java solution implements a function to determine the minimum number of days required to make a specified number of bouquets from a sequence of flower bloom days. The approach utilizes a binary search strategy to efficiently find the minimum day on which it's possible to prepare the required number of bouquets.

Here's an explanation of the key elements of the solution:

• The checkBouquets auxiliary method:

  • Takes an array of days each flower blooms, a maximum day, and the number of flowers needed per bouquet.
  • Iterates through each day, counting consecutive blooming flowers.
  • Resets the count whenever the day exceeds the current maximum considered day.
  • Counts and returns the number of possible bouquets that can be made under current conditions.

• The minDays method:

  • Determines the range of days to consider, setting high to the maximum value in the days array.
  • Employs binary search within this range:
    • Evaluates the mid-point as a potential solution by checking if enough bouquets can be made by this day.
    • Adjusts the search range based upon whether the mid-point was viable or not, narrowing down to the minimum required days.

• This approach ensures the solution remains efficient by reducing the potential solution space exponentially with binary search, avoiding a direct and slow linear search over potentially large input arrays.

With function minDays, the overall process returns the least number of days required so that m bouquets of k consecutive flowers each can be made. Note that a return value of -1 indicates it's impossible to make the required number of bouquets within the given days array.

class Solution:
    def calculate_bouquets(self, flower_days, current_day, bouquet_size):
        total_bouquets = 0
        consecutive_flowers = 0

        for bloom_time in flower_days:
            if bloom_time <= current_day:
                consecutive_flowers += 1
            else:
                consecutive_flowers = 0

            if consecutive_flowers == bouquet_size:
                total_bouquets += 1
                consecutive_flowers = 0

        return total_bouquets

    def minimum_days(self, flower_days, num_bouquets_needed, bouquet_size):
        if num_bouquets_needed * bouquet_size > len(flower_days):
            return -1

        low = 0
        high = max(flower_days)
        result_days = -1

        while low <= high:
            mid = (low + high) // 2

            if self.calculate_bouquets(flower_days, mid, bouquet_size) >= num_bouquets_needed:
                result_days = mid
                high = mid - 1
            else:
                low = mid + 1

        return result_days

The provided solution in Python tackles the problem of finding the minimum number of days required to form a specific number of bouquets from flowers that bloom on different days. The solution involves two main functions within the Solution class:

• calculate_bouquets(flower_days, current_day, bouquet_size): This function computes the number of bouquets that can be formed by the given current_day. It iterates through the list flower_days, counting consecutive flowers that have bloomed by or before current_day. Once the count matches the bouquet_size, a bouquet is made, and the count resets.

• minimum_days(flower_days, num_bouquets_needed, bouquet_size): This function determines the minimum number of days required to make at least num_bouquets_needed. It uses binary search to efficiently find the minimal day. Initially, it verifies if forming the required number of bouquets is feasible given the total number of flowers and bouquet_size. The binary search is conducted between the earliest and latest bloom days, constantly checking the middle value (mid) to see if the required number of bouquets can be formed by that day.

If it's feasible, the search continues to test earlier days to find the minimum. If forming the required bouquets ever becomes impossible, it returns -1.

The approach ensures that the solution is efficient and handles larger input sizes effectively by minimizing the number of necessary calculations, especially helpful when dealing with a range of bloom days and bouquet requirements.