_1482. Minimum Number of Days to Make m Bouquets.md

1482. Minimum Number of Days to Make m Bouquets

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 19, 2024

Last updated : July 12, 2024

---

Related Topics : Array, Binary Search

Acceptance Rate : 55.49 %

---

    Notes
    This seems a lot like merge intervals where we need to find how many days till
    sum(interval - remainder for interval in intervals) >= m * k

---

Solutions

• m1482 Dailly.py
• m1482 v2 Removed Helper.py

Python

m1482 Dailly.py

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

        flowers = [-1] * (len(bloomDay))    # flowers[i] = index of start of group
                                            # if val == -1, unused
                                            # if val < -1, -1 - val = size of grouping

        dayIndx = [(day, indx) for indx, day in enumerate(bloomDay)]
        dayIndx.sort(reverse=True)          # sorted so smallest day at top to pop

        def findStarter(indx: int) -> int :
            if indx == 0 or flowers[indx - 1] == -1 :
                return indx
            
            indx -= 1

            while flowers[indx] >= 0 :
                indx = flowers[indx]
            return indx

        flowersUsed = 0
        maxDay = 0
        while dayIndx and flowersUsed < m * k :
            day, indx = dayIndx.pop()
            maxDay = day
            
            starter = findStarter(indx)

            if indx == starter:    # is start of group
                flowers[indx] = -2
            else :                 # to the right of a group
                flowers[indx] = starter
                flowersUsed -= ((-1 - flowers[starter]) // k * k)
                flowers[starter] -= 1

            # merge right side if exit()
            # we don't have to worry about flowers used merging
            if indx < len(flowers) - 1 and flowers[indx + 1] < -1 :
                flowersUsed -= ((-1 - flowers[indx + 1]) // k) * k  # subtract right group
                flowers[starter] += flowers[indx + 1] + 1
                flowers[indx + 1] = starter

            flowersUsed += (-1 - flowers[starter]) // k * k

        return maxDay if k * m <= flowersUsed else -1

m1482 v2 Removed Helper.py

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:

        flowers = [-1] * (len(bloomDay))    # flowers[i] = index of start of group
                                            # if val == -1, unused
                                            # if val < -1, -1 - val = size of grouping

        dayIndx = [(day, indx) for indx, day in enumerate(bloomDay)]
        dayIndx.sort(reverse=True)          # sorted so smallest day at top to pop

        bouquetsCollected = 0
        day = 0
        while dayIndx and bouquetsCollected < m :
            day, indx = dayIndx.pop()

            starter = indx
            if not (indx == 0 or flowers[indx - 1] == -1) :
                starter -= 1
                while flowers[starter] >= 0 :
                    starter = flowers[starter]

            if indx == starter:    # is start of group
                flowers[indx] = -2
            else :                 # to the right of a group
                flowers[indx] = starter
                bouquetsCollected -= ((-1 - flowers[starter]) // k)
                flowers[starter] -= 1

            # merge right side if exit()
            # we don't have to worry about flowers used merging
            if indx < len(flowers) - 1 and flowers[indx + 1] < -1 :
                bouquetsCollected -= ((-1 - flowers[indx + 1]) // k)  # subtract right group
                flowers[starter] += flowers[indx + 1] + 1
                flowers[indx + 1] = starter

            bouquetsCollected += (-1 - flowers[starter]) // k

        return day if m <= bouquetsCollected else -1