Pentole e coperchi (Editoriale)

Ordiniamo in ordine crescente i raggi dei coperchi e i raggi delle pentole. Per la pentola più piccola troviamo il coperchio più piccolo con cui può essere coperta. Poi per la seconda pentola più piccola troviamo il coperchio più piccolo adatto a lei, e così via. La risposta sarà il numero di pentole che possono essere coperte con i coperchi.

Esempio

Consideriamo per quale numero massimo di pentole si possono trovare i coperchi corrispondenti per l'esempio dato.

Implementazione dell'algoritmo

Dichiariamo gli array in cui memorizzeremo i raggi delle pentole e dei coperchi.

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

Leggiamo i dati in input.

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]);

Ordiniamo i raggi delle pentole e dei coperchi.

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

Usando il metodo greedy, cerchiamo ogni volta il coperchio più piccolo con cui si può coprire la pentola più piccola.

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

Stampiamo il numero di pentole coperte.

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

Implementazione in Java

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();
  }
}  

Implementazione in Python

Leggiamo i dati in input.

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

Ordiniamo i raggi delle pentole e dei coperchi.

pan.sort()
lid.sort()

Usando il metodo greedy, cerchiamo ogni volta il coperchio più piccolo con cui si può coprire la pentola più piccola.

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

Stampiamo il numero di pentole coperte.

print(i)