Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The question to describe

The ith person’s weight is people[I], and the maximum weight each ship can carry is limit.

Each boat can carry up to two people at a time, provided that the combined weight of these people is maximum limit.

Return the number of boats needed to carry each person. (Make sure everyone gets on the boat).

Example 1:

Input: people = [1,2], limit = 3

Thinking analysis: greedy thinking analysis, double pointer plus sort, weight from small to large sort, the heaviest can bring a lightest, the number of not the heaviest can be reduced by 1, the lightest and heaviest can be reduced by 1, that is, pointer move.

Conclusion:

  • Minimum number of boats, 2 persons per boat
  • So let’s sort the people array
  • Double pointer, I starts from the first person, j starts from the last person
  • Compare whether the current sum of people referred to by I and j is less than limit
    • If so, the result is+ 1, marking that two people have been traversed currently, vis+2, and then moving the current I and j by one step
    • Repeat until I ===j
    • At the end of the current traverse, all the persons that can be loaded have been recorded, the remaining persons that are not on board, any two persons must not be loaded on the same boat at the same time

C + + version

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        // double pointer sort
        int left=0,right=people.size(a)- 1;
        sort(people.begin(),people.end());
        int ans=0;
        while(left<=right){
            if(limit-people[right]>=people[left]){
                left++;
            }
            right--;
            ans++;
        }
        returnans; }};Copy the code

Java version

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length,res = 0;
        for(int i = 0,j = n - 1; i <= j;) {if(people[i] + people[j] <= limit){
                i++;
            }
            j--;
            res++;
        }
        returnres; }}Copy the code