diff options
-rw-r--r-- | grumpy_bookstore_owner.c | 43 | ||||
-rw-r--r-- | grumpy_bookstore_owner.py | 45 |
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)) |