Problem statement

You are given an array people where people[i] is the weight of the i-th person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.

Example 1

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Example 2

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Example 3

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

Constraints

• 1 <= people.length <= 5 * 10^4.
• 1 <= people[i] <= limit <= 3 * 10^4.

Solution: Greedy

For each boat pick the heaviest person first. The remaining weight on that boat might be not enough for anyone else. Otherwise, let the lightest one go as well.

Example 2

For people = [3,2,2,1] and limit = 3:

• The heaviest one is 3. He reaches the limit. This boat can carry only him.
• The next heavy one is 2. This boat may carry one more with at most 1 in weight. The lightest one ( weight 1) satisfies that. They are on this same boat.
• The last boat carries the last person with weight 2.

Code

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int numRescueBoats(vector<int>& people, int limit) {
    sort(people.begin(), people.end(), greater<int>());
    int i = 0;
    int j = people.size() - 1;
    while (i <= j) {
        if (people[i] + people[j] <= limit) {
            j--;
        }
        i++;
    }
    return i;
}
int main() {
    vector<int> people{1,2};
    cout << numRescueBoats(people, 3) << endl;
    people = {1,2,3,2};
    cout << numRescueBoats(people, 3) << endl;
    people = {3,5,3,4};
    cout << numRescueBoats(people, 5) << endl;
}

Output:
1
3
4

Complexity

• Runtime: O(NlogN), where N = people.length.
• Extra space: O(1).