Editorial

Sort the radii of the lids and the radii of the saucepans in ascending order. For the smallest saucepan, find the smallest lid that can cover it. Then, for the second smallest pan, find the smallest lid that fits it, and so on. The answer will be the number of saucepans that can be covered with lids.

Example

Let’s find the maximum number of pans for which lids can be matched in the given example.

Algorithm realization

Declare arrays to store the radii of saucepans and lids.

#define MAX 1010
int pan[MAX], lid[MAX];

Read the input data.

scanf("%d %d",&n,&m);
for(i = 0; i < n; i++)
  scanf("%d",&pan[i]);
for(i = 0; i < m; i++)
  scanf("%d",&lid[i]);

Sort the radii of pans and lids.

sort(pan,pan+n);
sort(lid,lid+m);

Using the greedy method, search for the smallest lid each time that can cover the smallest pan.

for (i = j = 0; (i < n) && (j < m); j++)
  if (pan[i] <= lid[j]) i++;

Print the number of covered pans.

printf("%d\n",i);

Java realization

import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m = con.nextInt();
    Integer pan[] = new Integer[n];
    for(int i = 0; i < n; i++)
      pan[i] = con.nextInt();
   
    Integer lid[] = new Integer[n];
    for(int i = 0; i < m; i++)
      lid[i] = con.nextInt();
   
    Arrays.sort(pan);
    Arrays.sort(lid);

    int i = 0;
    for(int j = 0; (i < n) && (j < m); j++)
        if (pan[i] <= lid[j]) i++;
    
    System.out.println(i);
    con.close();
  }
}

Python realization

Read the input data.

n, m = map(int,input().split())
pan = list(map(int,input().split()))
lid = list(map(int,input().split()))

Sort the radii of pans and lids.

pan.sort()
lid.sort()

Using the greedy method, search for the smallest lid each time that can cover the smallest pan.

i = j = 0
while i < n and j < m:
  if pan[i] <= lid[j]: i += 1
  j += 1

Print the number of covered pans.

print(i)