###### 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:

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)