---
# System prepended metadata

title: 881. Boats to Save People
tags: [Leetcode, greedy, medium, python]

---

###### tags: `Leetcode` `medium` `greedy` `python`

# 881. Boats to Save People

## [題目連結:] https://leetcode.com/problems/boats-to-save-people/

## 題目:
You are given an array ```people``` where ```people[i]``` is the weight of the ```ith``` person, and an **infinite number of boats** where each boat can carry a maximum weight of ```limit```. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most ```limit```.

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


**Example 1:**
```
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
```
**Example 2:**
```
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
```
**Example 3:**
```
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
```

## 解題想法:
* 題目為
    * 每艘船容量limit，最多一次能座兩人
    * 無限船的情況下，求最少船隻能容納所有people

* 原本想法(錯誤)😢:
    * 最多乘坐len(peole)艘船:每人一艘
    * target=[limit] * len(people)
    * dfs 遍歷每個people可乘坐到的target[i]是否合法
    * 但沒考量到只能乘坐兩人........
    
* 正確想法:
    * 只能座兩人情況下: Greedy!!
    * 將數組由大到小排序好
    * 由兩pointer指向最胖與最瘦
        * fat=0
        * thin=len(people)-1
    * 每次希望容納是:(最胖+最瘦)組合
        * 成功配對:
            * 兩pointer一起移動
        * 不成功配對:
            * 胖子自己一組
        * res+=1

## Python:
``` python=
class Solution(object):
    def numRescueBoats(self, people, limit):
        """
        :type people: List[int]
        :type limit: int
        :rtype: int
        """
        #最多座兩人 Greedy
        people.sort(reverse=True) #由大到小
        fat=0
        thin=len(people)-1
        res=0
        while fat<=thin:
            if people[fat]+people[thin]<=limit: #成功配對
                fat+=1
                thin-=1
            else: #最胖的自己一組
                fat+=1
            res+=1
        return res

if __name__=='__main__':
    result=Solution()
    ans=result.numRescueBoats(people = [3,2,2,1], limit = 3)
    print(ans)
```

