Minimum Amount of Time to Fill Cups - Video Solutions

Problem Overview: You are given an array amount where each element represents the number of cold, warm, and hot cups to fill. Each second you can either fill two different types of cups or one cup of any type. The task is to compute the minimum number of seconds required to finish filling all cups.

Approach 1: Greedy Counting (O(1) time, O(1) space)

The key observation is that one second can process two different cup types simultaneously. The total work is the sum of all cups, but you cannot process more than one cup of the same type per second. Sort the three values or compute the maximum directly. The minimum time is max(max(amount), ceil(sum(amount)/2)). The first term handles the case where one type dominates, while the second term represents pairing cups whenever possible. This greedy reasoning avoids simulation and works in constant time because the array size is fixed. The approach relies on simple array manipulation and a classic greedy observation.

Approach 2: Priority Queue (Heap) Simulation (O(n log 3) time, O(1) space)

This method simulates the process using a max heap. Push the three cup counts into a priority queue. Each second, pop the two largest values, decrement both, and push them back if they are still positive. If only one type remains, decrement it alone. The heap ensures the two largest counts are always chosen, which maximizes parallel filling each second. Because the heap size never exceeds three elements, operations are cheap, but the loop runs for roughly the total number of seconds required.

Recommended for interviews: Interviewers usually expect the greedy observation. The heap simulation demonstrates understanding of priority queues, but the constant-time greedy formula shows stronger problem insight and leads to the most optimal solution.