แนวคิด
สมมติว่ากำลังพยายามแจกคุกกี้ให้เด็กๆ แต่ควรให้เด็กแต่ละคนได้สูงสุดหนึ่งคุกกี้ เด็กแต่ละคน i มี greed factor gi คือขนาดขั้นต่ำของคุกกี้ที่เด็กจะพอใจ และคุกกี้แต่ละชิ้น j มีขนาด sj เมื่อ sj >= gi สามารถมอบคุกกี้ j ให้เด็ก i ได้ และเด็ก i จะพอใจ เป้าหมายคือเพิ่มจำนวนเด็กที่พอใจให้มากที่สุดและแสดงจำนวนสูงสุด
เช่น ถ้าอินพุตคือ [1,2], [1,2,3] ผลลัพธ์คือ 2 มีเด็ก 2 คน คุกกี้ 3 ชิ้น Greed factors คือ 1, 2 มีคุกกี้ 3 ชิ้นขนาดพอที่จะทำให้เด็กทุกคนพอใจ ดังนั้นผลลัพธ์คือ 2
วิธีแก้:
- เรียงอาร์เรย์ g
- เรียงอาร์เรย์ s
- i := 0, j = 0
- while (i < ขนาด g และ j < ขนาด s): ถ้า g[i] <= s[j]: เพิ่ม i ขึ้น 1, เพิ่ม j ขึ้น 1
- คืนค่า i
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j]) i++;
j++;
}
return i;
}
};
main() {
Solution ob;
vector<int> v = {1,2}, v1 = {1,2,3};
cout << (ob.findContentChildren(v, v1));
}
อินพุต
{1,2}, {1,2,3}
เอาต์พุต
2
