881

881. Boats to Save People (Medium)

You are given an array people where people[i] is the weight of the ith 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 * 104
• 1 <= people[i] <= limit <= 3 * 104

Companies:
Salesforce, Amazon, Cisco, Uber

Related Topics:
Array, Two Pointers, Greedy, Sorting

Solution 1. Greedy

The first intuition is that we can greedily fill from heavy people or from light people. From heavy is more promising because we can use the light people to fill in the boats.

// OJ: https://leetcode.com/problems/boats-to-save-people/
// Author: github.com/lzl124631x
// Time: O(NlogD) where N is to total number of people
//                and D is the distinct count of weights.
// Space: O(D)
class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        map<int, int, greater<int>> m;
        for (int w : people) m[w]++;
        int ans = 0;
        while (m.size()) {
            int w = limit, cnt = 0;
            while (w > 0 && cnt < 2) {
                auto it = m.lower_bound(w);
                if (it == m.end()) break;
                w -= it->first;
                if (--it->second == 0) m.erase(it->first);
                ++cnt;
            }
            ++ans;
        }
        return ans;
    }
};

Solution 2. Greedy + Two Pointers

For the lightest person a, if a can pair with the heaviest person b, let a do so.

If not, then the heaviest person b can't pair with any one, let b go alone.

// OJ: https://leetcode.com/problems/boats-to-save-people/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int numRescueBoats(vector<int>& A, int limit) {
        sort(begin(A), end(A));
        int i = 0, j = A.size() - 1, ans = 0;
        while (i <= j) {
            ++ans;
            if (A[i] + A[j] <= limit) ++i;
            --j;
        }
        return ans;
    }
};