LeetCode 881: 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.

限制條件

• 1 <= people.length <= 5 * 104
• 1 <= people[i] <= limit <= 3 * 104

範例

• Example 1:
  Input: people = [1,2], limit = 3
Output: 1
  Explanation: 1 boat (1, 2)
• Example 2:
  Input: people = [3,2,2,1], limit = 3n = 1, bad = 1
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)

解法一：雙指針排序

解題思路

根據題目，每一艘船最多只能搭乘最多兩人。因此，最好的狀況就是將一重一輕的兩個乘客安排至同一艘船上，這樣就可以最小化所需船的總數。我們可以將輸入陣列排序後使用雙指針來實現這樣的想法。

步驟詳解

1. 初始化 boats_number 變數作為統計目前需要的總船數量。
2. 初始化雙指針 i 及 j 並分別從 people 陣列的頭尾開始移動。
3. 將 people 由小至大進行排序。
4. 當 i 指針小於等於 j 指針時，嘗試將在 i 及 j 位置的兩個人放至船上：
   1. 若兩人總重 (people[i] + people[j]) 小於等於 limit，代表我們可以將目前兩人用同一艘船載走。將 i 指針向右移動，並也將 j 指針向左移動。
   2. 若兩人總重大於 limit，表示目前這艘船只能將體重較大的人 (people[j]) 載走。將 j 指針向左移動。
   3. 將 boats_number 增加 1。
5. 最後回傳 boats_number。

程式碼

def num_rescue_boats(people: List[int], limit: int) -> int:
    boats_number = 0
    i = 0
    j = len(people) - 1

    people.sort()

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

    return boats_number

複雜度分析

• 時間複雜度：O(NlogN)，其中 N 為 people 的陣列長度。
• 空間複雜度：O(1)

參考資料

• LeetCode 原題出處：Boats to Save People – LeetCode