aboutsummaryrefslogtreecommitdiff
path: root/min_days_make_bouquets.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_days_make_bouquets.py')
-rw-r--r--min_days_make_bouquets.py45
1 files changed, 45 insertions, 0 deletions
diff --git a/min_days_make_bouquets.py b/min_days_make_bouquets.py
new file mode 100644
index 0000000..02cf2e2
--- /dev/null
+++ b/min_days_make_bouquets.py
@@ -0,0 +1,45 @@
+# 1482. Minimum Number of Days to Make m Bouquets
+
+"""
+given an integer array 'bloomDay', an integer 'm', and an integer 'k'. you
+want to make 'm' bouquets. to make a bouquet, you need to use 'k' adjacent
+flowers from the garden. the garden consists of 'n' flowers, the i'th flower
+will bloom in the 'bloomDay[i]' and then can be used in exactly one bouquet.
+return the minimum number of days you need to wait to be able to make 'm'
+bouquets from the garden. if it is impossible to make 'm' bouquets, return -1
+"""
+
+
+class Solution(object):
+ def minDays(self, bloomDay, m, k):
+ """
+ :type bloomDay: List[int]
+ :type m: int
+ :type k: int
+ :rtype: int
+ """
+ if m * k > len(bloomDay):
+ return -1
+ left, right = 1, max(bloomDay)
+ while left < right:
+ mid = (left + right) / 2
+ flow, bouq = 0, 0
+ for i in bloomDay:
+ flow = 0 if i > mid else flow + 1
+ if flow >= k:
+ flow = 0
+ bouq += 1
+ if bouq == m:
+ break
+ if bouq == m:
+ right = mid
+ else:
+ left = mid + 1
+ return left
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minDays(bloomDay=[1, 10, 3, 10, 2], m=3, k=1))
+ print(obj.minDays(bloomDay=[1, 10, 3, 10, 2], m=3, k=2))
+ print(obj.minDays(bloomDay=[7, 7, 7, 7, 12, 7, 7], m=2, k=3))