🚀 Sort + Greedy || Explained Intuition 🚀
Problem Description\n\nGiven an array happiness of length n representing the happiness values of n children standing in a queue, and a positive integer k, choos
# Problem Description\n\nGiven an array `happiness` of length `n` representing the happiness values of `n` children standing in a queue, and a positive integer `k`, choose `k` children from the queue in `k` turns. During each turn, selecting a child decreases the happiness value of all children not yet chosen by `1`. However, happiness values cannot become **negative**. Return the maximum sum of happiness values among the selected children.\n\nEx: `happiness` = [1,2,3], `k` = 2\nOutput: 4\nExplanation: Select 2 children as follows:\n1. Pick the child with happiness value 3. Remaining happiness values: [0,1].\n2. Pick the child with happiness value 1. Remaining happiness values: [0].\nSum of selected children\'s happiness values: 3 + 1 = 4.\n\n---\n\n# Intuition\n\nHi there, \uD83D\uDE04\n\nLet\'s dive\uD83E\uDD3F deep into our today\'s problem.\nIn today\'s problem, we have array of happiness indicates each child\'s happiness\uD83D\uDE04\uD83D\uDE14 in it and we have to choose `k` children in `k` turns (rounds).\nBUT we have to **max** the sum of those happiness.\uD83D\uDCC8\n\nHow can we do that ?\uD83E\uDD14\nlet\'s give you some hint.... now, we have to choose `k` children and `max` their sum so what we can do?\nYes, we can **sort** !\uD83E\uDD29\nwe can **sort** the children and choose the **maximum** `k` ones -we can use any other method to get the maximum `k` ones like using a **heap** but sort is my favorite\uD83D\uDE02-.\n\nwhat we can do in a nutshell is to **sort** those happiness `ascending` or `descending` you can use both -C++ and Python solutions are descending and Java solution in ascending-\nthen for each round we choose the (highest current happiness - past rounds till now).\n\nsince all happiness are **decreased** by `1` each round other than selected ones till now then when we choose a happiness in a round we will **decrease** from it the number of past round that we didn\'t select it in.\n\nand finally, we have our answer which is the sum of all selected happiness.\uD83D\uDE03\n\nAnd this is the solution for our today\'S problem I hope that you understood it\uD83D\uDE80\uD83D\uDE80\n\n---\n\n# Approach\n\n1. **Sort** the happiness values in `non-increasing` order.\n2. Initialize a variable `total` to store the total happiness sum.\n3. Iterate `k` times:\n    a. Calculate the happiness contribution of the current child in this turn by subtracting the turn number from their happiness value. If the result is **negative**, set it to `0`.\n    b. Add the calculated happiness contribution to the `total`.\n4. Return the `total` happiness sum.\n\n---\n\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        // Sort the happiness values in non-increasing order\n        sort(happiness.rbegin(), happiness.rend());\n\n        long long total = 0;\n        for (int turn = 0; turn < k; ++turn) {\n            // Calculate the happiness contribution of the current child in this turn\n            // since his happinness has been decreased for all of the past rounds\n            long long current = max(happiness[turn] - turn, 0);\n            // Accumulate the happiness contribution\n            total+= current;\n        }\n        return total;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        // Sort the happiness values in non-increasing order\n        Arrays.sort(happiness);\n\n        long total = 0;\n        for (int turn = happiness.length; happiness.length - turn < k; --turn) {\n            // Calculate the happiness contribution of the current child in this turn\n            // since his happiness has been decreased for all of the past rounds\n            long current = Math.max(happiness[turn - 1] - (happiness.length - turn), 0);\n            // Accumulate the happiness contribution\n            total += current;\n        }\n        return total;\n    }\n}\n```\n```Python []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        # Sort the happiness values in non-increasing order\n        happiness.sort(reverse=True)\n\n        total = 0\n        for turn in range(k):\n            # Calculate the happiness contribution of the current child in this turn\n            # since his happiness has been decreased for all of the past rounds\n            current = max(happiness[turn] - turn, 0)\n            # Accumulate the happiness contribution\n            total += current\n        \n        return total\n```\n\n\n![HelpfulJerry.jpg](https://assets.leetcode.com/users/images/f736826f-0d82-4480-952c-05d0a0ffb9c6_1700875279.2888722.jpeg)\n
['Greedy', 'Sorting', 'Python', 'C++', 'Java', 'Python3']