Minimum cost problem of breaking containers in $O(n\log n)$ Can anyone kindly give me some hint on solving this?
There are $n$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with capacity $c_i$ and initial water $a_i$ ($a_i&lt;c_i$).
In case of breakage of any container, all the water inside it will pour into the container below.
Each container will break if the water inside it is more than its capacity.
On the other hand, we can always break a container manually by paying the cost $p_i$.
Provide an algorithm to find the minimum cost to break the $n$th container in $O(n\log n)$.
Using a binary heap may be useful.
To solve this problem in $O(nlogn)$, We can use a min-heap.
Consider $s_i = \Sigma_{k=i}^{n}{a_k}$ and $b_i = s_i + c_i - a_i$. You can see that if $b_i - s_j &lt; 0$ for $j &lt; i$, by starting from $j$ and breaking every container from $j$ to $i$, container $i$ will break by the amount of water from the containers $j$ to $i$.
First set $cost = 0$ and $min = p_i$. Then do the following from $n$ to $1$:

Calculate $s_i$.
Calculate $b_i$.
Add $p_i$ to $cost$.
Add $b_i$ to the mean-heap and heapify it.
While $b_j - s_i &lt; 0$ ($b_j$ is the root of the heap): Remove the root and subtract $p_j$ from $cost$.
If $cost &lt; min$, update $min$.

At every container, we know that if we start from that container, we need to break some of them and the rest will break by the water. When we remove a container from the heap, we can be sure that if we start from that container, the removed container will break by itself, and the total cost will be to break the rest, so we can subtract the cost of breaking the removed container from the total cost.
Since the while loop is run once for each container, and the for loop runs n times, the total time will be $O(nlogn)$.