881. Boats to Save People

Problem

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)

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

Intuition

• Tóm tắt đề bài: Tìm số lần nhỏ nhất cần để vận chuyển hành khách i có trọng lượng là people[i] qua bên kia bờ sông sao cho mỗi chuyến chỉ được chở tối đa 2 người và tổng trọng lượng không được vượt quá limit
• Gần tương tự bài 2Sum: people[i] + people[j] <= limit (trong trường hợp chở 2 người 1 chuyến). Còn trường hợp chở 1 người 1 chuyến thì people[i] <= limit luôn đúng (theo constraint của đề bài)

Approach

• Sort people tăng dần theo trọng lượng
• Dùng 2 pointer left l và r duyệt từ đầu mảng và cuối mảng tiến vào trung tâm

Ví dụ: people = [5,1,4,2,6, 3] và limit = 6
Sau khi sort: \

Với people = [1, 2, 3, 4, 5, 6] và pointers: l = 0, r = 5
case 1: l != r và s = people[l] + people[r] = 7 > limit \ nên people[r] phải chở 1 mình, giảm con trỏ r 1 đơn vị r--. people[l] vẫn còn thể ghép cặp với 1 người khác nên không
tăng con trỏ left. Tại sao không tăng con trỏ left mà lại giảm con trỏ r? Vì mảng sort tăng dần, trỏ left tăng lên thì \ tổng s cũng tăng lên và luôn lớn hơn limit

people = [1, 2, 3, 4, 5, 6]
pointers: l = 0, r = 4
case 2: l != r và s = people[l] + people[r] = 6 <= limit nên people[l] và people[r] được chở cùng 1 chuyến => vì vậy tăng l++ và giảm r--\

Với people = [1, 2, 3, 4, 5, 6] và pointers: l = 1, r = 3
case 2: Tương tự trường hợp ngay kế trên, people[l] và people[r] được chở \ cùng 1 chuyến => vì vậy tăng l++ và giảm r--

Với people = [1, 2, 3, 4, 5, 6] và pointers: l = 2, r = 2
case 3: l=r và theo contrainst people[i] luôn <= limit nên với case l=r thì people[l] (or people[r]) được chở 1 mình

Sau khi đọc ví dụ trên, các case ở trên chính là điều kiện của câu lệnh if else ở phần implementation

Implementation

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;
        Arrays.sort(people);

        int count = 0;
        int r = n-1;
        for (int l = 0; l <= r;) {
            if (l == r) { // case 3
                l++;
            } else if (people[l] + people[r] <= limit) { // case 2
                l++;
                r--;
            } else { // case 1
                r--;
            }
            count++;
        }

        return count;
    }
}

Hoặc gọn hơn là

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        int n = people.length;

        Arrays.sort(people);

        int L = 0; int R = n-1;
        int counter = 0;

        while (L <= R) {
            int totalWeigth = people[L] + people[R];

            if (totalWeigth <= limit) {
                counter++;
                L++; R--;
            } else {
                // constraint: people[i] always less than limit
                // so we should carry the people[R] person first than people[L] since people[R] >= people[L]
                // this will help "minimum number of boats""
                counter++;
                R--;
            }
        }

        return counter;
    }
}