Simple Java Greedy solution beats 97% | O(nlogn) time and O(n) Space
Intuition\nA pretty standard Greedy problem. Just be greedy for the child with the maximum leftover happiness from among the not selected ones.\n\n# Approach\n1
# Intuition\nA pretty standard Greedy problem. Just be greedy for the child with the maximum leftover happiness from among the not selected ones.\n\n# Approach\n1. Sort the array.\n2. Iterate the array in descending order and the happiness value from the top k values while subtracting the number of elements already selected before the element.\n3. Return the sum.\n\n# Complexity\n- Time complexity:\nO(nlogn) // merge sort\n\n- Space complexity:\nO(n) // merge sort\n\n# Code\n```\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n\n        Arrays.sort(happiness);\n        long sum = 0;\n\n        for (int i = happiness.length - 1, j = 0; i >= 0 && j < k; i--, j++) {\n            sum = sum + Math.max(0, happiness[i] - j);\n        }\n\n        return sum;\n    }\n}\n```
['Greedy', 'Sorting', 'Java']