Skip to content

2335. Minimum Amount of Time to Fill Cups

Description

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

Solutions

Solution 1

Thinking

Each second we fill two different cups or one cup. The total is at most \(300\), so we may repeatedly decrement the two current maxima.

Sort, decrease the two largest (or one if the second is already \(0\)), and repeat until all are zero. Each second absorbs as much demand as possible.

1
2
3
4
5
6
7
8
9
class Solution:
    def fillCups(self, amount: List[int]) -> int:
        ans = 0
        while sum(amount):
            amount.sort()
            ans += 1
            amount[2] -= 1
            amount[1] = max(0, amount[1] - 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int fillCups(int[] amount) {
        int ans = 0;
        while (amount[0] + amount[1] + amount[2] > 0) {
            Arrays.sort(amount);
            ++ans;
            amount[2]--;
            amount[1] = Math.max(0, amount[1] - 1);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int fillCups(vector<int>& amount) {
        int ans = 0;
        while (amount[0] + amount[1] + amount[2]) {
            sort(amount.begin(), amount.end());
            ++ans;
            amount[2]--;
            amount[1] = max(0, amount[1] - 1);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func fillCups(amount []int) int {
    ans := 0
    for amount[0]+amount[1]+amount[2] > 0 {
        sort.Ints(amount)
        ans++
        amount[2]--
        if amount[1] > 0 {
            amount[1]--
        }
    }
    return ans
}

1
2
3
4
5
6
7
function fillCups(amount: number[]): number {
    amount.sort((a, b) => a - b);
    let [a, b, c] = amount;
    let diff = a + b - c;
    if (diff <= 0) return c;
    else return Math.floor((diff + 1) / 2) + c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
impl Solution {
    pub fn fill_cups(mut amount: Vec<i32>) -> i32 {
        amount.sort();
        let dif = amount[0] + amount[1] - amount[2];
        if dif <= 0 {
            return amount[2];
        }
        (dif + 1) / 2 + amount[2]
    }
}

Solution 2

Thinking

Method 1 simulates second by second. After sorting \(a \le b \le c\), a closed form exists: if \(a+b \le c\), the two smaller amounts finish inside \(c\) seconds; otherwise we always pair two cups, and the answer is \(\lfloor (a+b+c+1)/2 \rfloor\).

1
2
3
4
5
6
class Solution:
    def fillCups(self, amount: List[int]) -> int:
        amount.sort()
        if amount[0] + amount[1] <= amount[2]:
            return amount[2]
        return (sum(amount) + 1) // 2

1
2
3
4
5
6
7
8
9
class Solution {
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        if (amount[0] + amount[1] <= amount[2]) {
            return amount[2];
        }
        return (amount[0] + amount[1] + amount[2] + 1) / 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(), amount.end());
        if (amount[0] + amount[1] <= amount[2]) {
            return amount[2];
        }
        return (amount[0] + amount[1] + amount[2] + 1) / 2;
    }
};

1
2
3
4
5
6
7
func fillCups(amount []int) int {
    sort.Ints(amount)
    if amount[0]+amount[1] <= amount[2] {
        return amount[2]
    }
    return (amount[0] + amount[1] + amount[2] + 1) / 2
}

Comments