aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--grumpy_bookstore_owner.c43
-rw-r--r--grumpy_bookstore_owner.py45
2 files changed, 88 insertions, 0 deletions
diff --git a/grumpy_bookstore_owner.c b/grumpy_bookstore_owner.c
new file mode 100644
index 0000000..69330ca
--- /dev/null
+++ b/grumpy_bookstore_owner.c
@@ -0,0 +1,43 @@
+// 1052. Grumpy Bookstore Owner
+#include "leetcode.h"
+
+/*
+ * there is a bookstore owner that has a store open for 'n' miniutes. every
+ * minute some number of customers entre the store. you are given an integer
+ * array 'customers' of size 'n' where 'customers[i]' is the number of the
+ * customer that entres the store at the start of the i'th minute and all those
+ * customers leave after the end of that minute. on some minutes, the bookstore
+ * owner is grumpy. you are given an binary array 'grumpy' where 'grumpy[i]' is
+ * 1 if the bookstore owner is grumpy and zero otherwise. return the maximum
+ * number of customers that can be satisfied throughout the day.
+ */
+
+int maxSatisfied(int *customers, int customersSize, int *grumpy, int grumpySize,
+ int minutes) {
+ int total_satsified = 0, additional_satisfied = 0, curr = 0;
+ for (int i = 0; i < customersSize; i++)
+ if (!grumpy[i])
+ total_satsified += customers[i];
+ for (int i = 0; i < minutes; i++)
+ if (grumpy[i])
+ curr += customers[i];
+ additional_satisfied = curr;
+ for (int i = minutes; i < customersSize; i++) {
+ if (grumpy[i])
+ curr += customers[i];
+ if (grumpy[i - minutes])
+ curr -= customers[i - minutes];
+ if (curr > additional_satisfied)
+ additional_satisfied = curr;
+ }
+ return total_satsified + additional_satisfied;
+}
+
+int main() {
+ int c1[] = {1, 0, 1, 2, 1, 1, 7, 5}, g1[] = {0, 1, 0, 1, 0, 1, 0, 1},
+ c2[] = {1}, g2[] = {0};
+ printf("%d\n",
+ maxSatisfied(c1, ARRAY_SIZE(c1), g1, ARRAY_SIZE(c1), 3)); // expect: 16
+ printf("%d\n",
+ maxSatisfied(c2, ARRAY_SIZE(c2), g2, ARRAY_SIZE(c2), 1)); // expect: 1
+}
diff --git a/grumpy_bookstore_owner.py b/grumpy_bookstore_owner.py
new file mode 100644
index 0000000..7e1c669
--- /dev/null
+++ b/grumpy_bookstore_owner.py
@@ -0,0 +1,45 @@
+# 1052. Grumpy Bookstore Owner
+
+"""
+there is a bookstore owner that has a store open for 'n' miniutes. every
+minute some number of customers entre the store. you are given an integer
+array 'customers' of size 'n' where 'customers[i]' is the number of the
+customer that entres the store at the start of the i'th minute and all those
+customers leave after the end of that minute. on some minutes, the bookstore
+owner is grumpy. you are given an binary array 'grumpy' where 'grumpy[i]' is
+1 if the bookstore owner is grumpy and zero otherwise. return the maximum
+number of customers that can be satisfied throughout the day.
+"""
+
+
+class Solution(object):
+ def maxSatisfied(self, customers, grumpy, minutes):
+ """
+ :type customers: List[int]
+ :type grumpy: List[int]
+ :type minutes: int
+ :rtype: int
+ """
+ total_satisfied, additional_satisifed, curr = 0, 0, 0
+ for i in range(len(customers)):
+ if grumpy[i] == 0:
+ total_satisfied += customers[i]
+ customers[i] = 0
+ for i, time in enumerate(customers):
+ curr += time
+ if i >= minutes:
+ curr -= customers[i - minutes]
+ additional_satisifed = max(additional_satisifed, curr)
+ return total_satisfied + additional_satisifed
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxSatisfied(
+ customers=[1, 0, 1, 2, 1, 1, 7, 5],
+ grumpy=[0, 1, 0, 1, 0, 1, 0, 1],
+ minutes=3,
+ )
+ )
+ print(obj.maxSatisfied(customers=[1], grumpy=[0], minutes=1))