,800] Output: 5 Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

Constraints:

1 <= weight.length <= 10^3
1 <= weight[i] <= 10^3

Solution

Method 1 – Greedy + Sorting

Intuition

To maximize the number of apples in the basket without exceeding the weight limit, always pick the lightest apples first. This way, you can fit as many as possible before reaching the 5000 weight cap.

Approach

Sort the array of apple weights in ascending order.
Initialize a sum variable for the total weight and a counter for the number of apples.
Iterate through the sorted weights:
- Add the current apple's weight to the sum.
- If the sum exceeds 5000, stop and return the count.
- Otherwise, increment the count.
Return the count after the loop.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxNumberOfApples(vector<int>& weight) {\n        sort(weight.begin(), weight.end());\n        int sum = 0, ans = 0;\n        for (int w : weight) {\n            sum += w;\n            if (sum > 5000) break;\n            ++ans;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"

Related Tags