2 Easy Intuitive Solutions ✅
\n\n---\n# USING SORTING \u25FD\uFE0F\u25AB\uFE0F\u25AA\n\n---\n\n\n## Intuition\n Describe your first thoughts on how to solve this problem. \nSince we aim to 
\n\n---\n# USING SORTING \u25FD\uFE0F\u25AB\uFE0F\u25AA\n\n---\n\n\n## Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince we aim to maximize the happiness sum, it\'s intuitive to start by selecting children with higher happiness values. Sorting the array in decreasing order of happiness allows us to prioritize selecting children with higher happiness values first.\n\n## Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem can be approached **GREEDILY**. We want to maximize the happiness sum, so we should select children with higher happiness values first. **Sorting the array in decreasing order of happiness** accomplishes this. Then, we iterate through the sorted array, starting from the highest happiness value. In each iteration, we select a child and decrease the happiness of the remaining children accordingly.\n\n## Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSorting the array takes $$O(nlogn)$$ time, where $$n$$ is the number of children. The subsequent iteration takes $$O(k)$$ time. Thus, the overall time complexity is $$O(nlogn+k)$$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is $$O(1)$$ since we only use a constant amount of extra space.\n\n## Code\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        long long maxSum = 0;\n\n        // sort in decreasing order\n        sort(happiness.begin(), happiness.end(), greater<int>());\n\n        // select the first child\n        maxSum += max(0, happiness[0]);\n\n        // iterate through the remaining children\n        for (int i = 1; i < k; ++i) {\n            if (happiness[i] - i > 0)\n                maxSum += happiness[i] - i;\n        }\n\n        return maxSum;\n    }\n};\n```\n\n---\n\n# USING PRIORITY QUEUE (MAX-HEAP) \n\n## Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe use of a **max-heap (priority queue)** is intuitive because it allows us to efficiently select the children with the highest happiness values first. By maintaining a max-heap, we can always extract the child with the maximum happiness value in constant time.\n\n## Approach\n<!-- Describe your approach to solving the problem. -->\n1. We initialize a max-heap (`priority_queue`) and insert all the happiness values into it. Since it\'s a max-heap, the top element will always be the child with the highest happiness value.\n2. We iterate `k` times, representing the number of turns we can select children. In each iteration:\n    - We extract the top element (child with the highest happiness value) from the priority queue.\n    - We calculate the happiness value of the selected child, considering the happiness of previously selected children. Since we want to maximize the sum of happiness values, we take the maximum of the current happiness value minus the number of previously selected children (to account for the decrease in happiness of remaining children) and 0 (to ensure we don\'t add negative values to the sum).\n    - We update the `answer` by adding the calculated happiness value.\n    - We increment the `counter` to track the number of selected children.\n3. Finally, we return the maximum happiness sum obtained by selecting k children.\n\n\n## Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nBuilding the priority queue takes $$O(nlogn)$$ time, where $$n$$ is the number of children. Each of the k iterations takes$$ O(logn)$$ time to extract the maximum element from the priority queue. Thus, the overall time complexity is $$O(nlogn+klogn)$$.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is $$O(n)$$ to store the priority queue.\n\n## Code\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        long long ans = 0;\n\n        int count = 0;\n\n        priority_queue<int> pq; // max-heap\n\n        for(int &hap : happiness){\n            pq.push(hap);\n        }\n\n        for(int i = 0 ; i < k; i++){\n            int hap = pq.top();\n            pq.pop();\n\n            ans += max(hap-count, 0);\n\n            count++;\n        }\n        return ans;\n    }\n};\n```
['C++']