Teaching Kids Programming – Minimum Amount of Time to Fill Cups (Greedy Simulation Algorithm and Math)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You have a water dispenser that can dispense cold, warm, and hot water. Every second, you can either fill up 2 cups with different types of water, or 1 cup of any type of water. You are given a 0-indexed integer array amount of length 3 where amount[0], amount[1], and amount[2] denote the number of cold, warm, and hot water cups you need to fill respectively. Return the minimum number of seconds needed to fill up all the cups.

Example 1:
Input: amount = [1,4,2]
Output: 4
Explanation: One way to fill up the cups is:
Second 1: Fill up a cold cup and a warm cup.
Second 2: Fill up a warm cup and a hot cup.
Second 3: Fill up a warm cup and a hot cup.
Second 4: Fill up a warm cup.
It can be proven that 4 is the minimum number of seconds needed.

Example 2:
Input: amount = [5,4,4]
Output: 7
Explanation: One way to fill up the cups is:
Second 1: Fill up a cold cup, and a hot cup.
Second 2: Fill up a cold cup, and a warm cup.
Second 3: Fill up a cold cup, and a warm cup.
Second 4: Fill up a warm cup, and a hot cup.
Second 5: Fill up a cold cup, and a hot cup.
Second 6: Fill up a cold cup, and a warm cup.
Second 7: Fill up a hot cup.

Example 3:
Input: amount = [5,0,0]
Output: 5
Explanation: Every second, we fill up a cold cup.

Constraints:
amount.length == 3
0 <= amount[i] <= 100

Minimum Amount of Time to Fill Cups (Greedy Simulation)

To fill up a cup, it is the same as the opposite which is to reduce the amount of water from a cup.

We want to drink two cups with the most water first. For any single cup, we can only decrement one at a time, thus it takes N seconds to finish it. If we don’t pick the largest, the total time will not decrement. Therefore, we need to take the largest one, which may also decrement the second largest if there is any.

So, the strategy is greedy, we sort the cups, and for a second/iteration, we decrement the largest two until all numbers are zero or less.

The time complexity is O(Max(A)) – sorting 3 numbers is O(1) time/space complexity.

1
2
3
4
5
6
7
8
9

class Solution:
    def fillCups(self, A: List[int]) -> int:
        ans = 0
        while max(A) > 0:
            A.sort()
            ans += 1
            A[-1] -= 1
            A[-2] -= 1
        return ans

class Solution:
    def fillCups(self, A: List[int]) -> int:
        ans = 0
        while max(A) > 0:
            A.sort()
            ans += 1
            A[-1] -= 1
            A[-2] -= 1
        return ans

Minimum Amount of Time to Fill Cups (Math)

If the largest cup is bigger than the sum of the other two, we can always take/decrement the largest amount and consume other two (bring those to zeros). Otherwise, we should be able to take two until the last cup or two. Therefore, we can sum all the amounts and divide it by two.

The time complexity is O(1) constant – as there are 3 numbers only, and the math is quick.

1
2
3
4
5
6

class Solution:
    def fillCups(self, A: List[int]) -> int:
        A.sort()
        if A[0] + A[1] <= A[2]:
            return A[2]
        return ceil(sum(A) / 2)

class Solution:
    def fillCups(self, A: List[int]) -> int:
        A.sort()
        if A[0] + A[1] <= A[2]:
            return A[2]
        return ceil(sum(A) / 2)

The ceil function refers to the situation when we have a last cup, which requires still a second to complete, and it can be rewritten as :

1

return (sum(A)+1)//2

return (sum(A)+1)//2

Similarly, we can get the maximum value of the largest amount, and the sum/2 – whichever is larger.

1

return max(max(A), (sum(A)+1)//2)

return max(max(A), (sum(A)+1)//2)

–EOF (The Ultimate Computing & Technology Blog) —