881. Boats to Save People

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

Difficulty : Medium

Solution

Bucket sort

class Solution {

    public int numRescueBoats(int[] people, int limit) {
        //先用bucket sort 计算每个weight里人的个数
        //如果weight是limit，那么1个人就需要一只船
        int[] buckets = new int[limit + 1];
        for (int p : people) {
            buckets[p]++;
        }

        //如果people的重量是limit，那么有多少个人就需要多少只船
        int ans = buckets[limit];
        //然后从左边和右边向中间扫描，如果最小的重量和最大的重量的和 <= limit, 那么这2个人一条船
        int l = 1;
        int r = limit - 1;//limit 已经处理过了
        while (l <= r) {
            while (l <= r && buckets[l] <= 0) {
                //如果某个bucket里没有人， 就继续往右边处理
                l++;
            }
            while (l <= r && buckets[r] <= 0) {
                //如果某个bucket里没有人， 就继续往左边处理
                r--;
            }
            if (l > r) {
                break;
            }
            if (l + r <= limit) {
//                不能这样处理因为 如果 l == r, 比如[3,3] limit 6,那么 bucket[l] =2,bucket[r] = 2
//                最后的结果就是2， 实际上一条船就可以了
//                int min = Math.min(buckets[l], buckets[r]);
//                ans += min;
//                buckets[l] -= min;
//                buckets[r] -= min;
                ans++;
                buckets[l]--;
                buckets[r]--;
            } else {
                //r 太大了， 只能一个人一条船
                ans += buckets[r];
                r--;
            }
        }
        return ans;

    }
}