Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Satisfy the least greedy children first — they are the easiest to please.
  2. 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);
    }
}

Solve Assign Cookies online · All practice problems