【Day 67 】2021-11-15 - 881. 救生艇

[azl397985856]

881. 救生艇

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/boats-to-save-people/

前置知识

暂无

题目描述

第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1：

输入：people = [1,2], limit = 3 输出：1 解释：1 艘船载 (1, 2) 示例 2：

输入：people = [3,2,2,1], limit = 3 输出：3 解释：3 艘船分别载 (1, 2), (2) 和 (3) 示例 3：

输入：people = [3,5,3,4], limit = 5 输出：4 解释：4 艘船分别载 (3), (3), (4), (5) 提示：

1 <= people.length <= 50000 1 <= people[i] <= limit <= 30000

[yanglr]

思路:

题意: 保证每个人都能被船载, 即max(people) <= limit.

先进行排序, 方便后面能配成一组的体重, 也方便去重.

方法: 贪心 + 双指针

接下来使用贪心+双指针来做.

贪心的方向: 每个船最多装2个人, 而不是每个船尽量装得重量最大, 这两个条件是有优先级的. 根据这个限制我们每次用1个船装最大的1个之后，看看还能不能再装1个, 再装1个最小的即可.

代码:

实现语言: C++

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int minCount = 0;
        const int len = people.size();
        int left = 0, right = len - 1;
        // while的条件使用<= 是因为体重可能有重复的
        while (left <= right)  /* 贪心的方向: 每个船最多装2个人. 根据这个限制我们每次用1个船装最大的1个之后，看看还能不能再装1个, 再装1个最小的即可 */
        {
            if (people[left] + people[right] <= limit)
            {
                left++;
                right--;
            }
            else right--;
            minCount++;
        }

        return minCount;
    }
};

复杂度分析

• 时间复杂度: O(n log n)
• 空间复杂度: O(1)

[ysy0707]

思路：贪心+双指针

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        //people根据体重升序排序
        Arrays.sort(people);
        //两个指针，l从轻的开始遍历，r从重的开始遍历，res记录需要的船数量
        int l = 0, r = people.length - 1;
        int res = 0;

        while(l <= r){
            //如果l和r对应体重相加小于等于limit说明这俩可以组队
            if(people[l] + people[r] <= limit){
                r--;
                l++;
                res++;
            }
            //如果i和j不可以组队，说明剩下的都不可能组队成功，
            //j先上船，i等下一次看看能不能和下一个j组队
            else{
                r--;
                res++;
            }
        }
        return res;
    }
}

时间复杂度: O(NlogN) 空间复杂度: O(1)

[a244629128]

let numRescueBoats = function(people, limit) {
    let count=0,i=0,j=people.length-1;
    people.sort(function(a,b){
        return (a-b);
    });
    console.log(people,'people-after sort');
    while(i<=j){
        if(people[i]+people[j]<=limit){
            count++;
            i++;
            j--;
        }
        else{
            count++;
            j--;
        }
    }
    return count;
};

[Zhang6260]

JAVA版本

思路：可以使用双指针的来完成。船只能载二个人，那么最重的人只能尝试和最轻的人进行组合，如果大于limit的话，这最重的人只能单独过，反正则可以进行组合。

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

时间复杂度：O(nlog n)//主要是是排序算法的

空间复杂度：O(1）

[itsjacob]

Intuition

• [tags] greedy
• load one person on boat, and find the next people in the crowd that can fit in the same boat, delete both of them from the crowd

Implementation

class Solution
{
public:
  int numRescueBoats(vector<int> &people, int limit)
  {
    int maxWeight = *std::max_element(people.begin(), people.end());
    std::vector<int> weights(maxWeight + 1, 0);
    for (auto const &p : people) {
      weights[p]++;
    }
    int count{ 0 };
    for (auto const &p : people) {
      if (weights[p] != 0) {
        count++;
        weights[p]--;
        for (int left = std::min(limit - p, maxWeight); left > 0; left--) {
          if (weights[left] > 0) {
            weights[left]--;
            // at most 2 people on one boat, so we can break if we find two people
            break;
          }
        }
      }
    }
    return count;
  }
};

Complexity

• Time complexity: O(nm), where n is people.size() and m is max{max{people}, limit}
• Space complexity: O(m), where m is max{people}

[for123s]

代码

• 语言支持：C++

C++ Code:

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

[cicihou]

'''
贪心的思想就是寻找局部最优解

1. 题目要求船数最少，i.e. 每艘船尽量多装一些重量
2. 每次装人先将最大重量的装上，然后从轻到重遍历剩下的人，看剩余容量能否再装下一个人

由于每艘船限制只能载两个人，最轻的人搭配最重的人，对于我们来说是最少计算的局部最优解

如果最轻的人 a 和最重的人 b 重量和超过了 limit，那么其他人不用看了，肯定都不行。
如果最轻的人 a 可以和最重的人 b 同时载运，此时会存在另外一种方案（选择非最轻的人 c 和最重的人 b 配对）比其更优么？
答案是不能的，因为每艘船只能载两个人，即使运了 非最轻的人 c + 最重的人 b，最轻的人 a 还是需要占用一艘船的位置，需要的船数目还是一样的

最轻的人能跟最重的人配对，那就能和任何一个人配对
如果把最重的给了第二轻的，那么最轻的也只能去跟第二重的配对，事实上还是浪费了船的配重
'''

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        '''
        Greedy + two-pointer
        消耗掉一艘船，最重的人无论如何都走了一个，最轻的人如果满足要求也能运走
        完成遍历时，一共消耗的船的数量，就是我们想要的结果

        time: O(nlogn)
        space: O(1)
        '''
        people.sort()
        i = 0
        j = len(people) - 1
        res = 0
        while i <= j:
            res += 1
            if people[i] + people[j] <= limit:
                i += 1
            j += 1
        return res

[zhy3213]

思路

贪心+双指针

代码

    def numRescueBoats(self, people: List[int], limit: int) -> int:
        sp=sorted(people)
        res=0
        l,r=0,len(sp)-1
        while l<=r:
            res+=1
            if sp[l]+sp[r]<=limit:
                l+=1
                r-=1
                continue
            r-=1
        return res

[joeytor]

思路

先对数组进行排序

使用两个指针指向头和尾, 如果当前最重的和最轻的都可以上船 (指针的头和尾), 那么让这两个上一艘船, 否则让体重重的上船, 更新尾部的指针

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people)-1
        num = 0

        while i <= j:
            if people[i] <= limit - people[j]:
                i += 1
            j -= 1
            num += 1

        return num

复杂度

时间复杂度: O(nlogn) 排序的时间复杂度是 O(nlogn), 遍历的时间复杂度是 O(n)

空间复杂度: O(logn) 排序的空间复杂度

[xinhaoyi]

class Solution { public int numRescueBoats(int[] people, int limit) { //贪心算法 //people从小到大排序 //让当前一个体重最小的人和一个体重尽可能大的人先凑在一起上一艘船 //即让people[i]和people[j]上一艘船，i < j，如果找不到这个j，只让i上船即可 //如果让people[i]和people[j-1]上一艘船，如果people[i+1]和people[j]能挤一起，就扯平了，否则就损失了一艘船 //如果让people[i+1]和people[j]上一艘船，如果他们能上一艘船的话，那么剩下的people[i]肯定可以和people[j-1]上一艘船，就扯平了 //但是如果他们上不去的话，就只有people[i+1]一个人一艘船，这样损失一艘，或者people[i+1]和people[j-1]一艘船，这样扯平了 //综上，我这可以得到最优解 Arrays.sort(people); int count = 0; int length = people.length; int pos = 0; for(int j = length - 1; j > pos; j--){ while(pos < j && people[pos] + people[j] <= limit){ //一次两个人都能上船 pos += 1; j--; //count代表装了两个人的船的数量， count ++; } }

    //到这里，后面的人都只能一人一艘了，直接用总人数 - 装了两个人的船数
    return length - count;
}

}

[florenzliu]

Explanation

• greedy approach: sort the array people by its weight first
  • at most two persons: we can use two pointers, put the current lightest and the current heaviest in the remaining people on the same boat
  • if the sum is larger than the limit, put the heaviest alone in a boat, move to the next heaviest one
  • otherwise, move to the next lightest and the next heaviest

Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people)-1

        count = 0
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
            count += 1
            j -= 1
        return count  

Complexity:

• Time Complexity: O(nlogn)
• Space Complexity: O(1)

[flagyk5]

'''
时间 nlogn
空间 1
思路 排序之后，最大加上最小重量<=limit，他们上一条船。不行的话，最大重量单独一条船，
双指针往中间收。这题不存在最小重量被其他重量替代上船的问题，贪心是可以的
'''

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        n = len(people)
        a,b,ans = 0,n-1,0
        while a <= b:
            if people[a]+people[b] <= limit:
                a += 1
            b -= 1
            ans += 1
        return ans 

[zhangzz2015]

思路

• 对重量进行排序，优先装最大重量，看是否能搭配一个最小重量，是否小于limit，具体实现和two sum 双指针方法类似，先对people 重量进行排序，利用两端双指针方法，如果最大和最小people的重量小于等于limit，则两人可做一条boat，count++，left ++, right--，否则装载最大重量的1人，count++, right--, left不变。最后返回count 数目，时间复杂度为O(nlogn+n)，空间复杂度为O(1)

  关键点

• sort + 双指针

代码

• 语言支持：c

c Code:

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

        sort(people.begin(), people.end()); 

        int left =0; 
        int right = people.size()-1; 
        int count =0; 
        while(left <=right)
        {
            if(left!=right && people[right]+people[left]<=limit)
            {
                right--; 
                left++; 
                count++; 
            }
            else
            {
                right--; 
                count++; 
            }
        }

        return count; 
    }
};

[yachtcoder]

Interesting problem. O(nlgn), O(1)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        ret = 0
        l, r = 0, len(people) - 1
        while l <= r:
            if people[l] + people[r] <= limit:
                ret += 1
                l += 1
                r -= 1
            else:
                ret += 1
                r -= 1
        return ret

[biancaone]

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        if not people:
            return 0
        people.sort()

        i, j = 0, len(people) - 1
        result = 0

        while i <= j:
            result += 1
            if people[i] + people[j] <= limit:
                j -= 1
                i += 1
            else:
                j -= 1

        return result

[q815101630]

首先先sort， 然后按照最小配最大的放上船

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        ans = 0
        left = 0
        right = len(people)-1
        while left<=right:
            if left == right:
                ans+=1
                break
            if people[left]+people[right] <= limit:
                left+=1
                right-=1
                ans+=1
            else:
                right-=1
                ans+=1

        return ans

时间 O(nlogn) 空间O(1)

[pophy]

思路

• 贪心策略
• 排序people
• 优先让体重最轻的 L 和 最重的 R 进行配对 看是否小于limit
  • 小于Limit L++ / R --/ count++
  • 否则 大体重的自己坐船 R-- / count++

Java Code

    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int count = 0, l = 0, r = people.length-1;
        while (l <= r) {
            if (people[r] + people[l] > limit) {
                count++;
                r--;
            } else {
                l++;
                r--;
                count++;
            }
        }
        return count;
    }

时间&空间

• 时间 O(nlog(n))
• 空间 O(1)

[zhangyalei1026]

思路

排序 + 双指针

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        new = sorted(people)
        left, right = 0, len(people) - 1
        output = 0
        while left <= right:
            if new[left] + new[right] > limit:
                right -= 1
            else:
                left += 1
                right -= 1
            output += 1
        return output

复杂度分析

时间复杂度：O(nlogn) 空间复杂度: O(1)

[Daniel-Zheng]

思路

贪心。

代码(C++)

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int left = 0, right = people.size() - 1, res = 0;
         while (left <= right) {
             if (people[left] + people[right] <= limit) left++;
             right--;
             res++;
         }
        return res;
    }
};

复杂度分析

• 时间复杂度：O(NLogN)
• 空间复杂度：O(LogN)

[ZacheryCao]

Idea:

Greedy + Two pointers. Sort people first. Set up two pointers p1, p2. p1 starts from 0 and moves to right. p2 starts from end and moves to left. Every time, when people[p1] + people[p2] <= limit, add boats by one and move p1 to one step right, p2 one step to left. If people[p1] + people[p2] > limit, we have to let people[p2] alone have one boat and move p2 one step to left.

Code:

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people = sorted(people)
        ans = 0
        i, j = 0, len(people) - 1
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
                j -= 1
            else:
                j -= 1
            ans += 1
        return ans

Complexity:

Time: O(N log N). N is the length of the people array. We use sort whose complexity is O( N log N). For two pointers, it's O(N) Space: O(N)

[chang-you]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int res = 0;

        while (left <= right) {
            res++;
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
        }

        return res;
    }
}

[CoreJa]

思路

今天题目比较简单，但一定要注意审题"一艘船最多坐俩人！"

直接把人按体重排序，轻的匹配重的。如果最轻的都匹配不了重的，那重的就得自己坐一搜。

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        count = 0
        left, right = 0, len(people) - 1
        while left <= right:
            if people[left] + people[right] > limit:
                right -= 1
            else:
                left += 1
                right -= 1
            count += 1

        return count

[thinkfurther]

思路

尝试装最重和最轻的

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort(reverse=True)

        boat_count = 0

        heavy = 0
        light = len(people) - 1
        while heavy < light:
            if people[heavy] + people[light] <= limit:
                boat_count += 1
                heavy += 1
                light -=1
            else:
                boat_count += 1
                heavy += 1

        if light >= heavy:
            boat_count += 1

        return boat_count

代码

时间复杂度：O(NlogN)

空间复杂度：O(1)

[shawncvv]

思路

排序+双指针

代码

JavaScript Code

var numRescueBoats = function (people, limit) {
  people.sort((a, b) => a - b);
  let ans = 0,
    start = 0,
    end = people.length - 1;
  while (start <= end) {
    if (people[end] + people[start] <= limit) {
      start++;
      end--;
    } else {
      end--;
    }
    ans++;
  }
  return ans;
};

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[yan0327]

思路： 贪心思路学习之 看清条件：小艇最多两个人，从大到小遍历=》若能装下最小的，则左移最小端。 双指针+ 贪心

func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)
    out := 0
    l,r := 0,len(people)-1
    for l <= r{
        if people[l]+people[r]<=limit{
            l++
        }
        r--
        out++
    }
    return out
}

时间复杂度：O（nlogn） 空间复杂度：O(1)

[ginnydyy]

Problem

https://leetcode.com/problems/boats-to-save-people/

Notes

• Greedy
• Key point is a boat can take 2 people max.
• Need to sort the array, each boat will definitely take the currently heaviest people (at the right end of the array), then try if can take the currently lightest people.
• So need to use two pointers to point the front and end of the array, then update the pointers accordingly based on whether can take the lightest people each time.
• Details: while loop condition should be left <= right, not left < right, otherwise, when left == right, this case will be ignored.

Solution

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        if(people == null || people.length == 0){
            return 0;
        }
        Arrays.sort(people);
        int res = 0;
        int left = 0;
        int right = people.length - 1;
        while(left <= right){
            res++;
            if(people[left] + people[right] <= limit){
                left++;
            }
            right--;
        }

        return res;

    }
}

Complexity

• Time: O(nlogn). n is the length of the given people array. O(nlogn) for sorting the array. O(n) for using two pointers to traverse the array. For each traversal, it takes O(1) to process. Overall O(nlogn).
• Space: Depends on the sorting algorighm. Other than the extra space reuired by the sorting, other space is constant O(1).

[shixinlovey1314]

Title:881. Boats to Save People

Question Reference LeetCode

Solution

First Sort the people array, then use 2 pointers one from the start and one from the end, if the person at the start and the person at the end can board the same boat (less than limitit) move both start and end, otherwise, board the person at the end and move end to end - 1

Code

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        std::sort(people.begin(), people.end());
        int result = 0;
        int s = 0;
        int e = people.size() - 1;

        while (s <= e) {
            if (people[s] + people[e] <= limit) {
                s++;
                e--;
            } else {
                e--;
            }

            result++;
        }

        return result;
    }
};

Complexity

Time Complexity and Explanation

O(nlogn) for sorting

Space Complexity and Explanation

O(1)

[heyqz]

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        start, end = 0, len(people) - 1
        boat = 0
        people.sort()

        while start <= end:
            if people[start] + people[end] <= limit:
                start += 1
            end -= 1
            boat += 1

        return boat

time complexity: O(nlogn) space complexity: O(1)

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int num = 0;
        int left = 0;
        int right = people.length-1;
        Arrays.sort(people);
        while(left<=right){
            if(people[left]+people[right] <= limit) left++;
            right--;
            num++;
        }
        return num;
    }
}

[mannnn6]

代码

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;
        Arrays.sort(people);
        int light = 0, heavy = people.length - 1;
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {
                ++light;
            }
            --heavy;
            ++ans;
        }
        return ans;
    }
}

复杂度

时间复杂度：O（nlogn） 空间复杂度：O(logn)

[okbug]

思路

先排序 由于题目给出，所有的人质量都小于limit，所以排序后最大的也只能小于等于limit，并且一艘船只能做两个人 所以使用双指针，选一个最大的和最小的，如果坐不下，那么只要做一个最大的，所以右指针往左移，如果做的下的话，就左右两个指针都往里面移动。 并且不管怎么样，每次判断都是需要去耗费一艘船的，所以答案要每次都加一。

代码

function numRescueBoats(people: number[], limit: number): number {
    people.sort((a, b) => a - b);
    let res = 0;
    let i = 0, j = people.length - 1;
    while (i <= j) {
        if (people[i] + people[j] <= limit) {
            i++;
        }
        j--;

        res ++;
    }

    return res;
};

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());

        int res = 0, i = 0, j = people.size() - 1;

        while (i <= j) {
            if (people[i] + people[j] <= limit) {
                i ++;
            }
            j --;
            res ++;
        }

        return res;
    }
};

[ghost]

题目

881. Boats to Save People

思路

Greedy

代码

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        res = 0
        i, j = 0, len(people)-1

        while(i<=j):

            if people[i] + people[j] <= limit: i+=1
            j-=1
            res+=1

        return res

复杂度

Space: O(1) Time: O(nlogn)

[chun1hao]

var numRescueBoats = function (people, limit) {
    people.sort((a, b)=> a-b)
    let len = people.length
    let i = 0    
    let j = len-1
    let ans = 0
    while(i<=j){
        if(people[j] + people[i] <= limit){
            i++            
        }
        j--
        ans++
    }
    return ans
};

[shamworld]

思路

贪心，先排序，通过双指针表示左边为轻的，右边为重的进行计算

代码

var numRescueBoats = function(people, limit) {
    people.sort((a,b)=>a-b);
    let res = 0;
    let left = 0,right = people.length-1;
    while(left<=right){
        if(people[left]+people[right]<=limit) left++;
        res++;
        right--;
    }
    return res;
};

复杂度分析

• 时间复杂度:O(nlogn)
• 空间复杂度:O(n)

[JiangyanLiNEU]

Idea

• One boat can have maximum 2 people, so heaviest + lightest, if this can't work, then heaviest have to go solo
• Runtime = O(nlogn), Space = O(1)

  JavaScript

  var numRescueBoats = function(people, limit) {
  people.sort((a,b) => a-b);
  let left, right;
  left = 0;
  right = people.length-1;
  let result= 0;
  while (left <= right){
      result++;
      if (left==right){
          left++;
      }else{
          if (people[left] + people[right] <= limit){
              left++;
              right--;
           }else{
              right--;
           };
      }; 
  };
  return result;
  };

  Python

  class Solution(object):
  def numRescueBoats(self, people, limit):
      people.sort()
      left = 0
      right = len(people)-1
      res = 0
      while left<=right:
          res += 1
          if left != right:
              if (people[left]+people[right] <= limit):
                  left += 1
                  right -= 1
              else:
                  right -= 1
          else:
              left += 1
      return res

[asaoba]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int ans = 0;
        while (left <= right) {
            if (people[l] + people[r] <= limit) 
                 l++;
            right--;
            ans++;
        }
        return ans;
    }
}

[Francis-xsc]

思路

贪心算法，双指针 对数组排序，指针指向最轻的和最重的 如果二者和大于limit，则这艘船只能装下最重的，r-- 否则，可以装下二者，l++,r--

代码

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

复杂度分析

• 时间复杂度：O(NlogN)，其中 N 为数组长度。
• 空间复杂度：O(logN)

[wenlong201807]

代码块

var numRescueBoats = function(people, limit) {
  people.sort((a, b) => a - b)
  let j = people.length - 1
  let i = 0
  let ans = 0
  while (i < j) {
      if (people[j] + people[i] > limit) {
          j --
      } else {
          j --
          i ++
      }
      ans ++
  }

  if (i === j) {
      ans ++
  }

  return ans
};

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[ZJP1483469269]

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length;
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            if (people[l] + people[r] <= limit) l++;
            r--;
            ans++;
        }
        return ans;
    }
}

[watermelonDrip]

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        j = 0
        res = 0

        for i in range(len(people)-1,-1,-1):
            if j > i:
                return res
            if people[i]== limit:
                res+=1
            else:
                if people[i] + people[j] > limit:
                    res+=1
                else:
                    j+=1
                    res+=1

        return res

[akxuan]

思路

很典型的贪心， 满足条件即可 有个小弯儿不太好绕过来， 就是如果最大值和 次小值满足， 那要不要优先次小。 因为这个题每个船就两个， 那次小就留给次大就好了。

时间复杂度 排序的 nlogn + n 空间复杂度： 1

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        res = 0
        people.sort(reverse=True)

        start = 0
        end = len(people)-1

        while start <=end :
            if people[start] + people[end] <= limit :

                end -=1

            start += 1

            res += 1

        return res

[KennethAlgol]

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

[yingliucreates]

link:

https://leetcode.com/problems/boats-to-save-people/

代码 Javascript

const numRescueBoats = (people, limit) => {
    people.sort((a, b) => a - b);
    for (var i = 0, j = people.length - 1, boats = 0; i <= j; ++boats) { 
        people[j--] + people[i] <= limit && ++i;
    }
    return boats;
};

[ai2095]

881. Boats to Save People

https://leetcode.com/problems/boats-to-save-people/

Topics

• Greedy

思路

Greedy

代码 Python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        left, right = 0, len(people) - 1
        res = 0
        while left < right:
            if people[left] + people[right] <= limit:
                res += 1
                left += 1
                right -= 1
            elif people[right] <= limit:
                res += 1
                right -= 1

        if left == right:
            res += 1

        return res

复杂度分析

DP 时间复杂度： O(NlogN)
空间复杂度：O(1)

[septasset]

Day 67

代码(Python)

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        ans = 0
        people.sort()
        p1 = 0
        p2 = len(people)-1
        while p1<p2:
            if people[p1]+people[p2]<=limit: 
                p1+=1
                p2-=1
                ans+=1
            else:
                p2-=1
                ans+=1
        return ans if p1>p2 else 1+ans

[HondryTravis]

思路

贪心，考虑体重最轻的人

代码

var numRescueBoats = function (people, limit) {
  let ans = 0
  people.sort((a, b) => a - b)

  let light = 0, heavy = people.length - 1

  while (light <= heavy) {
    if (people[light] + people[heavy] <= limit) light++
    heavy--
    ans++
  }
  return ans
};

复杂度分析

时间复杂度 O(nlogN)

空间复杂度 O(logN)

[jaysonss]

思路

贪心算法，将最轻和最重的两个人放到一艘船上

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        if(people.length==0)return 0;
        Arrays.sort(people);
        int count = 0;
        int start =0,end = people.length-1;

        while(start<=end){
            if(people[start]+people[end]<=limit){
                start++;
                end--;
            }else {
                end--;
            }
            count++;
        }
        return count;
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(1)

[pan-qin]

Idea:

The heavy people should be paired with light people. If it can't be paired to the lightest people current available, it should be placed in a single boat. So sort the people array first, then pair people from head and tail.

Complexity:

Time: O(nlogn) Space: O(1)

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int len = people.length;
        if(len<=1)
            return len;
        Arrays.sort(people);
        int count = 0;
        int i=0, j=len-1;
        while(i<j) {
            if(people[i]+people[j]<=limit) {
                count++;
                i++;
                j--;
            }
            else {
                count++;
                j--;
            }
        }
        if(i==j)
            count++;
        return count;

    }
}

[nonevsnull]

思路

• 拿到题的直觉解法
  • 注意题目条件，每船最多两人；
  • 那就看重的能不能带上轻的了，能带上就带上，带不上就自己一船；

AC

代码

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0, right = people.length - 1, res = 0;
        while(left <= right){
            res++;
            if(people[left] + people[right] <= limit){
                left++;
            }
            right--;
        }
        return res;
    }
}

复杂度

time: O(NlogN) space: O(1)

[jocelinLX]

class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: people.sort() res=0 i=0 j=len(people)-1 while i<=j: if people[i]+people[j] > limit: j-=1 else: j-=1 i+=1 res+=1 return res