Practice › Greedy
Assign Cookies
Easy · Greedy · Asked at Amazon, TCS, Infosys, Wipro
Child i is content with a cookie of size ≥ g[i]. Each child gets at most one cookie and each cookie goes to at most one child. Print the maximum number of content children.
Input
Line 1: n. Line 2: n greed values. Line 3: m. Line 4: m cookie sizes.
Output
The maximum number of content children.
Constraints
- 1 ≤ n, m ≤ 3·10^4
Sort both; give each child the smallest cookie that satisfies them.
Example 1
Input
3 1 2 3 2 1 1
Output
1
Example 2
Input
2 1 2 3 1 2 3
Output
2
Hints
- Satisfy the least greedy children first — they are the easiest to please.
- Sort both lists. Walk the cookies in increasing size; give a cookie to the current child if it is big enough, otherwise throw that cookie away.
Approach
Sort greed values and cookie sizes. With pointers i (child) and j (cookie): if cookie[j] >= greed[i], the child is content, so move to the next child. Either way move to the next cookie. A cookie too small for the least greedy remaining child is too small for everyone, so skipping it costs nothing. Giving each child the smallest cookie that fits is the exchange-argument proof that greedy is optimal.
Complexity: O(n log n + m log m) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<int> g(n);
for (auto &x : g) cin >> x;
cin >> m;
vector<int> s(m);
for (auto &x : s) cin >> x;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0;
for (int j = 0; j < m && i < n; j++)
if (s[j] >= g[i]) i++;
cout << i << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
g = sorted(data[1 : n + 1])
m = data[n + 1]
s = sorted(data[n + 2 : n + 2 + m])
i = 0
for size in s:
if i < n and size >= g[i]:
i += 1
print(i)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] g = new int[n];
for (int i = 0; i < n; i++) g[i] = sc.nextInt();
int m = sc.nextInt();
int[] s = new int[m];
for (int i = 0; i < m; i++) s[i] = sc.nextInt();
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
for (int j = 0; j < m && i < n; j++)
if (s[j] >= g[i]) i++;
System.out.println(i);
}
}