2 solutions Heap && sorting || Easy Intuitive C++ Solution 💯
Intuition\n\nThe problem seems to revolve around maximizing the happiness sum under certain constraints. By observing the provided code, it seems like the algor
# Intuition\n\nThe problem seems to revolve around maximizing the happiness sum under certain constraints. By observing the provided code, it seems like the algorithm is prioritizing higher values of happiness to maximize the sum.\n\n# Approach\n\n1. **Priority Queue**: The algorithm utilizes a priority queue to efficiently access the highest happiness values. This allows it to greedily select the highest happiness values first.\n2. **Iteration**: The algorithm iterates `k` times to select the top `k` happiness values from the priority queue.\n3. **Happiness Sum Calculation**: For each iteration, it calculates the difference between the top happiness value and the counter. This difference is added to the happiness sum.\n4. **Counter Update**: The counter is incremented after each iteration to ensure that each subsequent iteration selects the next highest happiness value.\n5. **Break Condition**: The iteration stops if either `k` becomes 0 or the top happiness value becomes less than or equal to the counter.\n\n# Complexity\n\n- **Time Complexity**: The time complexity of building the priority queue is O(nlogn), where n is the size of the input happiness vector. The iteration runs for at most `k` times, each time involving operations like pushing and popping from the priority queue, which take O(logn) time. Therefore, the overall time complexity is O((n + k)logn).\n- **Space Complexity**: The space complexity is O(n) to store the priority queue. No additional space is used in the algorithm.\n\n\n# Code\n# Using Priority Queue\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        \n        priority_queue<int> pq;\n        long long counter = 0, happysum = 0;\n\n        for(auto it: happiness){\n            pq.push(it);\n        }\n\n        while(k--){\n\n            if(pq.top() - counter <= 0){\n                break ;\n            }\n\n            happysum += pq.top() - counter;\n            counter++;\n            pq.pop();\n\n        }\n\n        return happysum ;\n\n    }\n};\n```\n# Using Sorting\n\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        sort(begin(happiness), end(happiness), greater<int>());\n        int i = 0;\n        long long res = 0;\n\n        while(k--) {\n            happiness[i] = max(happiness[i] - i, 0);\n            res += happiness[i++];\n        }\n\n        return res;\n    }\n};\n```
['Sorting', 'Heap (Priority Queue)', 'C++']