Boats to Save People ใน C++

คำอธิบายปัญหา

มีคนแต่ละคนน้ำหนัก people[i] เรือแต่ละลำรับได้สูงสุด 2 คน และน้ำหนักรวม <= limit ต้องการหาจำนวนเรือน้อยที่สุด

ตัวอย่าง: [3,2,1,2], limit=3 → 3 เรือ ([1,2], [2], [3])

วิธีแก้ปัญหา (Two Pointers + Greedy)

1. เรียงน้ำหนักจากน้อยไปมาก
2. two pointers: i=ซ้าย (เบา), j=ขวา (หนัก)
3. ถ้า people[i] + people[j] <= limit: ขึ้นเรือคู่กัน (i++, j--)
4. มิฉะนั้น: คนหนักขึ้นคนเดียว (j--)
5. นับเรือทุกครั้ง

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        sort(people.begin(), people.end());
        int i = 0, j = people.size() - 1;
        int boats = 0;
        while(i <= j) {
            if(people[i] + people[j] <= limit) {
                i++;
                j--;
            } else {
                j--;
            }
            boats++;
        }
        return boats;
    }
};

int main() {
    vector<int> v = {3,2,1,2};
    Solution ob;
    cout << ob.numRescueBoats(v, 3);
    return 0;
}

อินพุต

[3,2,1,2] 3

เอาต์พุต

3