# TDA | practica 1 ejercicio 13 INCOMPLETO ## Consigna - Tenemos dos conjuntos de personas y para cada persona sabemos su habilidad de baile. **Queremos armar la máxima cantidad de parejas de baile**, sabiendo que para cada pareja **debemos elegir exactamente una persona de cada conjunto de modo que la diferencia de habilidad sea menor o igual a 1** (en módulo). - Además, cada persona puede pertenecer a lo sumo a una pareja de baile. Por ejemplo, si tenemos un multiconjunto con habilidades `{1, 2, 4, 6}` y otro con `{1, 5, 5, 7, 9}`, la máxima cantidad de parejas es 3. Si los multiconjuntos de habilidades son `{1, 1, 1, 1, 1}` y `{1, 2, 3}`, la máxima cantidad es 2. - a) Considerando que ambos multiconjuntos de habilidades estan ordenados en forma creciente, observar que la solución se puede obtener recorriendo los multiconjuntos en orden para realizar los emparejamientos - b)Diseñar un algoritmo goloso basado en a) que recorra una única vez cada multiconjunto. Explicitar la complejidad temporal y espacial auxiliar. - c) Demostrar que el algoritmo dado en b) es correcto. ## Resolución ```python def parejas(lista1:list, lista2:list)->int: parejas = 0 # contador de parejas válidas i = 0 # indice para lista1 j = 0 # indice apra lista2 ## Algoritmo greedy: while i < len(lista1) and j < len(lista2): habilidad1 = lista1[i] habilidad2 = lista2[j] if habilidad1 > habilidad2: criterio = habilidad1 - habilidad2 else: criterio = habilidad2 - habilidad1 if criterio <= 1: parejas += 1 i += 1 j += 1 elif habilidad1 < habilidad2 and criterio > 1: i += 1 elif habilidad2 < habilidad1 and criterio > 1: j += 1 return parejas ```