LeetCode Hasta Top 1% — Día 73

Resolviendo LeetCode hasta estar en el top 1 por ciento — Día 73

Problema: 1792 Maximum Average Pass Ratio en LeetCode ver en LeetCode

Dificultad: Media

Etiquetas: Greedy, Heap, Matemáticas, Priority Queue

Resumen del problema

Tienes n clases. Cada clase tiene p alumnos aprobados de un total t. Dispones de extraStudents alumnos adicionales que siempre aprobarán. Puedes asignarlos uno a uno a cualquier clase. Objetivo: distribuirlos para maximizar el promedio de ratios de aprobados entre todas las clases.

Idea y razonamiento

Enfoque fuerza bruta: probar todas las distribuciones posibles explota combinatoriamente, ya que el número de formas crece como n elevado a extraStudents.

Enfoque óptimo con avaricia greedy: añadir un alumno a distintas clases aporta beneficios desiguales al promedio. La clave es medir el incremento marginal que aporta un alumno en cada clase y siempre elegir la clase con mayor ganancia en cada paso.

Función de ganancia

Para una clase con p aprobados y t en total, la ganancia de añadir un alumno que aprueba es: gain p, t = (p+1) dividido entre (t+1) menos p dividido entre t

Intuición

Antes de añadir el alumno, el ratio es p dividido entre t. Después es p mas 1 dividido entre t mas 1. La diferencia es la mejora exacta que esa clase aporta al promedio si recibe el siguiente alumno. Para maximizar el promedio total, en cada iteración asignamos el alumno a la clase con mayor ganancia. Esto se implementa eficientemente con un heap de máximos almacenando las ganancias marginales.

Algoritmo

1. Calcular la ganancia inicial para cada clase y meterla en un heap de máximos junto con p y t.

2. Repetir extraStudents veces extraer la clase con mayor ganancia, actualizarla sumando uno a p y t, recalcular su ganancia y devolverla al heap.

3. Al final, promediar los ratios p dividido entre t de todas las clases.

Complejidad

Tiempo: O de n mas extraStudents por log n, ya que cada inserción y extracción del heap cuesta log n y hacemos n inicializaciones mas extraStudents asignaciones.

Espacio: O de n por el heap.

Puntos clave

La función de ganancia es el insight central para cuantificar el beneficio marginal.

Un heap de máximos permite seleccionar siempre la mejor clase de forma eficiente.

Muchos problemas de asignación se resuelven con el patrón medir ganancia marginal, elegir máximo, actualizar.

Autorrevisión

Entendimiento del porqué: la mejora marginal es decreciente y avaricia por ganancia local maximiza el promedio global con heap.

Capacidad de recuerdo: alta, es un patrón clásico de avaricia con cola de prioridad.

Aplicación práctica y conexión con Q2BSTUDIO

En Q2BSTUDIO aplicamos este tipo de estrategias de optimización en proyectos reales de software a medida y aplicaciones a medida, desde asignación de recursos hasta scheduling inteligente. Si tu empresa busca construir soluciones eficientes con datos y algoritmos, nuestro equipo puede diseñar, desarrollar y desplegar la solución end to end. Conoce más sobre cómo creamos plataformas robustas y escalables en nuestro servicio de desarrollo de software y aplicaciones a medida.

Además, somos especialistas en inteligencia artificial e ia para empresas. Desde modelos de clasificación y recomendación hasta agentes IA con razonamiento y planificación incremental tipo heap, integramos estas capacidades con servicios cloud aws y azure, ciberseguridad y gobierno del dato. Descubre cómo impulsamos tu estrategia con IA en nuestra página de inteligencia artificial.

Palabras clave que trabajamos y entregamos en proyectos reales

software a medida, aplicaciones a medida, inteligencia artificial, ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio, ia para empresas, agentes IA, power bi

Progreso personal

Día 73

Problemas resueltos totales 434

Confianza de hoy Alta

LeetCode rating 1530

Conclusión

El truco para Maximum Average Pass Ratio es priorizar por ganancia marginal con un heap. Este patrón es reutilizable en optimización de promedios, planificación de recursos y mejora iterativa en múltiples dominios de negocio. Si deseas llevar este tipo de enfoques a tus productos digitales con calidad empresarial y seguridad, en Q2BSTUDIO combinamos ingeniería de software a medida, agentes IA, servicios cloud y analítica con power bi para crear valor real y sostenible.