Solution

Method 1 – Greedy with Min-Heap

Intuition

To maximize the sum, we want to pick the largest possible elements from the matrix, but we must respect the per-row limits and the overall limit of k elements. We can collect the allowed elements from each row, sort them, and pick the top k.

Approach

For each row, sort the elements in descending order and take up to limits[i] elements.
Collect all selected elements from all rows into a single list.
Sort the combined list in descending order.
Pick the top k elements and sum them for the answer.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxSumWithAtMostKElements(vector<vector<int>>& grid, vector<int>& limits, int k) {\n        vector<int> pool;\n        for (int i = 0; i < grid.size(); ++i) {\n            auto row = grid[i];\n            sort(row.rbegin(), row.rend());\n            for (int j = 0; j < min((int)row.size(), limits[i]); ++j)\n                pool.push_back(row[j]);\n        }\n        sort(pool.rbegin(), pool.rend());\n        int ans = 0;\n        for (int i = 0; i < mi

Related Tags