boats-to-save-people

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>people</code> where <code>people[i]</code> is the weight of the <code>ith</code> person, and an infinite number of boats where each boat can carry a maximum weight of <code>limit</code>. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most <code>limit</code>.

Return the minimum number of boats to carry every given person.

&nbsp;
Example 1:

<pre>
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
</pre>

Example 2:

<pre>
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
</pre>

Example 3:

<pre>
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= people.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= people[i] &lt;= limit &lt;= 3 * 104</code></li>
</ul>

numRescueBoats

Boats to Save People

Greedy

Array

Two Pointers

Sorting

给定数组<meta charset="UTF-8" />&nbsp;<code>people</code>&nbsp;。<code>people[i]</code>表示第 <code>i</code>&nbsp;个人的体重&nbsp;，船的数量不限，每艘船可以承载的最大重量为&nbsp;<code>limit</code>。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为&nbsp;<code>limit</code>。

返回 承载所有人所需的最小船数&nbsp;。

&nbsp;

示例 1：

<pre>
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
</pre>

示例 2：

<pre>
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
</pre>

示例 3：

<pre>
输入：people = [3,5,3,4], limit = 5
输出：4
解释：4 艘船分别载 (3), (3), (4), (5)</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= people.length &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= people[i] &lt;= limit &lt;= 3 * 104</code></li>
</ul>