Daily 04/05/2024: [881. Boats to Save People](https://leetcode.com/problems/freedom-trail/)

# 1. Tóm tắt đề bài
Bạn được cung cấp một mảng ```people``` trong đó ```people[i]``` là trọng lượng của người thứ ```i``` và vô số thuyền trong đó mỗi thuyền có thể chở trọng lượng tối đa là ```limit```. Mỗi thuyền chở tối đa hai người cùng một lúc, với điều kiện tổng trọng lượng của những người đó không quá ```limit```.

Trả về số thuyền ít nhất để chở mỗi người .

#### Giới hạn
- $1 \le$ ```people.length```$\le 5 \cdot 10^4$
- $1 \le$ ```people[i]``` $\le$ ```limit``` $\le 3 \cdot 10^4$

# 2. Tóm tắt lời giải

#### Phân tích
- Bài không hề khó vì đề bài đã giới hạn chỉ chở hai người, nên chúng ta chỉ việc lần lượt chở thằng lớn nhất và thằng bé nhất hiện tại là được. Nếu mà thằng lớn đủ rồi thì chỉ chở thằng lớn thôi.
- VD: ```[1, 2, 3, 4, 5]``` . ```Limit = 5``` đi chẳng hạn
- Thì các thuyền của chúng ta chở lần lượt là
- (5), (1, 4), (2, 3)
- Đây là kết quả của một dạng toán tham lam. Việc chứng minh sẽ dành cho bạn đọc.

# 3. Lời giải chi tiết
#### Thuật toán
- Sắp xếp lại mảng people
- Xét những ông nặng nhất xem có nhét được ông bé nào lên thuyền không.

#### Code

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

#### Độ phức tạp
$O(nlog(n))$ do tính thêm lệnh sort.

# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần khá nhẹ nhàng.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Sorting, Greedy</span>