“This is the 21st day of my participation in the First Challenge 2022. For details: First Challenge 2022”

This paper presents a two-pointer solution to the “lifeboat” problem

Topic:

Given an array of people. People [I] is the weight of the ith person, there is no limit to the number of boats, and the maximum weight each boat can carry is the 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 maximum number of boats needed to carry everyone.

Example 1: Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 Ship (1, 2) Example 2: Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 1 ship (1, 2) example 2: Input: people = [3,2,2,1], limit = 3 Example 3: Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 ships load (3), (3), (4), (5)Copy the code

Note:

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104

Their thinking

A. what B. what C. what D. what

  1. Each person’s weight should not exceed the limit;
  2. Each boat is limited to two persons;
  3. The weight of each vessel shall not exceed the limit;

We can consider sorting the given array, selecting the heaviest person first and seeing if it can share a boat with the smallest person. If so, let them stay together. If not, then the heaviest person will definitely not be paired with everyone else, so leave him alone.

Then, see if the person with the second heaviest weight can be paired with the person with the lowest weight (assuming that the maximum weight is single), and so on.

Without loss of generality, let’s first sort and then consider using double Pointers. Initially, two Pointers point to both ends:

When the heaviest person was alone, the pointer moved one place to the center;

When the person with the highest weight and the person with the lowest weight pair up, their hands move one place to the middle.

Code thread:

  1. The sorting
  2. Initialize a double pointer
  3. Traverse, each time using the heaviest and lightest pair, if the two weight is less than or equal to limit, the light aboard (left++). No matter whether the lightest are on board or not, all the heavy ones must be on board. Number of ships required + 1 (nums++)

JavaScript implementation:

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort((a,b)=>(a-b))
    let left = 0
    let right = people.length-1
    let nums=0
    while(left<=right){
        if(people[left]+people[right]<=limit){
            left++
        }
        right--
        nums++
    }
    return nums
};
Copy the code

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~