Maximize Happiness of Selected Children

Leetcode Question Link

For the convenience, we use $a[i]$ to denote $\text{happiness}[i]$ in article below.

Analysis

Gain From One Child

Consider if we chose children $i$ at time $t,t\in [0,k)$, what could we add to the final sum?

If not considering our choice, the lost of the happiness $L$ should be:

$$L(i)=min(a[i],k)$$

• If $a[i]\le k$, this means the $a[i]$ will goes to $0$ before the procedure finished, so the maximum decrease of the value is from $a[i]$ to $0$, that is, $L=a[i]$
• If $a[i]>k$, that means $a[i]$ never reach $0$, the decrease value is exactly the round $k$. So we have $L=k$.

Now take our choice operation into consideration. If we chose a child at time $t$, then the actual lost of happiness of this child should be:

$$L_A(i,t)=min(L(i),t)$$

• If $t<L$, means we chose this child while it’s decreasing, this means if we chose this child, it should be decreasing from time $0$ to time $t$, the actual decrease value $L_A=t$.
• If $t>L$, means this child’s happiness already stop decreasing, our action of choice actually has no effect, so $L_A=L$.

---

In conclusion, we could know that for any child $i$, if we choice it, the happiness value $H$ we could get will be:

$$\begin{array}{rl}H(i,t)& =a[i]-L_A(i,t)\\ & =a[i]-min(min(a[i],k),t)\\ & =a[i]-min(a[i],k,t)\end{array}$$

Choose Child

Based on analysis above, we should be aware that the greedy strategy could be used for this question. That is, to ensure highest final sum, we should always choose child with largest initial happiness first.

Consider the formula of $H(i,t)$:

$$H(i,t)=a[i]-min(a[i],k,t)$$

If we want to make $H(i,t)$ larger, we need to make $min(a[i],k,t)$ smaller, so we should put larger $a[i]$ with smaller $t$. And that, in this problem, means choose child with larger happiness sooner.

Code

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
 
using std::priority_queue;
using std::vector;
 
bool debug = false;
 
struct MyMinHeap : std::priority_queue<int, std::vector<int>, std::greater<int>> {
    void reserve(size_t n) { this->c.reserve(n); }
};
 
class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int k) {
        // min heap
        MyMinHeap maxk;
        maxk.reserve(k);
        int cur, top;
 
        // initial heap with k elements
        for (int i = 0; i < k; ++i) {
            maxk.push(happiness[i]);
        }
        // iterate while update
        for (int i = k; i < happiness.size(); ++i) {
            cur = happiness[i];
            top = maxk.top();
 
            // current elements smaller, just continue
            if (cur <= top) {
                continue;
            }
            // update elements
            maxk.pop();
            maxk.push(cur);
        }
 
        // at this point, all max-k elements are in the min heap
 
        long long answer = 0;
        int chooseTime, lost;
        for (chooseTime = k - 1; chooseTime >= 0; --chooseTime) {
            // get top element
            cur = maxk.top();
            maxk.pop();
 
            if (debug) {
                cout << "choosed: " << cur << endl;
            }
 
            // determine the lost of this element
            lost = std::min({k, cur, chooseTime});
 
            // update answer
            answer += (cur - lost);
        }
 
        return answer;
    }
};