leetcode：881. lifeboat

Title source

• leetcode：881. lifeboat

Title Description

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    

    }
};

title

greedy + Double pointer

（1） Go through the array first , If a person weighs more than limit, Then return to infinity , It means that you can't decide how many ships

（2） Then sort , Slide from the middle dividing point to the left and right

• look for <= limit/2 The rightmost position , As L The pointer
• Find the first one more than limit/2 The location of , As R The pointer
• see L Location and R Can we get a boat together , You can't , exceed

• L Move to the left …L Arrived 3, Sure
  

• Don't assign boats first ,R Slide right , Slide all the way to R If you go down one more step, you can't follow 3 Gather up a boat

• The starting point of greed ： from 3 Start to the left 6 individual , Go to consume the one on the right 6 individual , It must be the most economical

（3） give an example ： The right side is exhausted first

（4） give an example ： The left side is exhausted first

$$shipOfCountThe\; amount=\frac{\times CountThe\; amount}{2}+\frac{\surd CountThe\; amount}{2}+RightSideRemnantNextOfCountThe\; amount$$

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    
        if(people.empty()){
    
            return 0;
        }
        
        int N = people.size();
        std::sort(people.begin(), people.end());
        if(people[N - 1] > limit){
    
            return -1;
        }
        
        int lessR = -1;
        for (int i = N - 1; i >= 0; --i) {
    
            if(people[i] <= limit/2){
    
                lessR = i;
                break;
            }
        }
        
        if(lessR == -1){
    
            return N;
        }
        
        int L = lessR;
        int R = lessR + 1;
        int noUsed = 0;
        while (L >= 0){
    
            int solved = 0;
            while (R < N && people[L] + people[R] <= limit){
    
                solved++;
                R++;
            }
            if(solved == 0){
    
                noUsed++;
                L--;
            }else{
    
                L = std::max(-1, L - solved);
            }
        }
        int all = lessR + 1;
        int used = all - noUsed;
        int moreUnsolved = (N - all) - used;
        return used + ((noUsed + 1) >> 1) + moreUnsolved;
    }
};

Double pointer

class Solution {
    
public:
    int numRescueBoats(vector<int>& people, int limit) {
    
        int N = people.size();
        std::sort(people.begin(), people.end());
        if(people[N - 1] > limit){
    
            return -1;
        }
        
        int ans = 0, l = 0, r = N - 1, sum = 0;
        while (l <= r){
    
            sum = l == r ? people[l] : people[l] + people[r];
            if(sum > limit){
    
                r--;
            }else{
    
                l++;
                r--;
            }
            ans++;
        }
        return ans;
    }
};