✅Easy✨||C++|| Beats 100% || With Explanation ||
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves selecting children from a queue to maximize the sum of their happi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves selecting children from a queue to maximize the sum of their happiness values. Each time a child is selected, the happiness of all unselected children decreases by 1.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort the Happiness Values: Sort the happiness values in non-increasing order to prioritize selecting children with higher happiness values.\n2. Iterate Through the Sorted Values: Iterate through the sorted happiness values.\n. For each happiness value, if it is greater than the index (position) of the child in the sorted order and there are still turns left (k > 0), select the child.\n. Increment the answer by the difference between the happiness value and the index.\n. Decrease the number of turns available (k) after selecting a child.\n3. Return the Maximum Happiness Sum: Return the maximum sum of happiness achieved by selecting children.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n. Sorting the happiness values takes O(n log n) time, where n is the number of children.\n. The loop iterates through the sorted happiness values, taking O(n) time.\n. Overall, the time complexity is O(n log n).\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(1) as the algorithm only uses a constant amount of extra space.\n\n# Code\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& hap, int k) {\n        ios_base::sync_with_stdio(false);\n        cin.tie(NULL);\n        long long ans = 0;\n        sort(hap.begin(), hap.end(), greater<int>());\n        int n = hap.size();\n        for(int i = 0; i < n; i++) {\n            if(hap[i] <= i) break;\n            if(k == 0) break;\n            ans += hap[i] - i;\n            k--;\n        }\n        return ans;\n    }\n};\n```
['C++']