1196

1196. How Many Apples Can You Put into the Basket (Easy)

You have some apples and a basket that can carry up to 5000 units of weight.

Given an integer array weight where weight[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.

 

Example 1:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

Example 2:

Input: weight = [900,950,800,1000,700,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 <= 103
• 1 <= weight[i] <= 103

Companies:
Virtu Financial

Related Topics:
Array, Greedy, Sorting

Solution 1.

// OJ: https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maxNumberOfApples(vector<int>& A) {
        sort(begin(A), end(A));
        int sum = 0, i = 0, N = A.size();
        while (i < N && sum + A[i] <= 5000) sum += A[i++];
        return i;
    }
};