Entrevista técnica de código: ¿Cómo maximizar la recompensa con trabajos no superpuestos?

Prompt y casos de uso

Cada trabajo es (start, end, reward). Elija trabajos compatibles con la recompensa total máxima; se permite un tiempo de finalización igual al siguiente inicio. Para (1,3,50), (3,5,40), (2,6,100), los dos primeros trabajos ganan con una recompensa de 90. Esta es una pregunta de coding que evalúa la ordenación de intervalos, la búsqueda de predecesores y la programación dinámica, independientemente del lenguaje de implementación.

El material público de algoritmos utiliza la programación de intervalos/trabajos ponderados como un ejercicio de programación dinámica y patrones de intervalos, y un relato público de entrevista también registra una variante de programación de intervalos. Indique requisitos verificables sin afirmar una frecuencia de entrevistas no comprobable.

Qué evalúa el entrevistador

• Si ordena por tiempo de finalización para que el último trabajo elegido cree una decisión ordenada.
• Si define p(i), el último trabajo que finaliza a más tardar cuando comienza el trabajo i.
• Si compara omitir y tomar el trabajo actual en lugar de tomar de forma codiciosa la recompensa individual más grande.
• Si la búsqueda binaria reduce la búsqueda del predecesor a O(log n) y si puede reconstruir los trabajos elegidos.
• Si maneja end == start, tiempos de finalización iguales, entrada vacía y recompensas iguales a cero.

Aclaraciones antes de responder

• ¿Son compatibles los tiempos de inicio y fin iguales? Esta respuesta asume que sí: end <= start.
• ¿Pueden las recompensas ser negativas? De ser así, permita explícitamente no elegir ningún trabajo, con una línea base de 0.
• ¿Se requiere solo la recompensa máxima? Este artículo también reconstruye el conjunto de trabajos; omita los datos del padre si no son necesarios.
• ¿Son los tiempos números enteros? El ordenamiento solo necesita comparabilidad; la búsqueda binaria no necesita enteros consecutivos.
• ¿Se puede seleccionar un trabajo dos veces? Asuma que cada trabajo de entrada se puede seleccionar como máximo una vez.
• ¿Puede ocurrir start > end? Rechácelo o normalícelo antes de la recurrencia; no oculte datos no válidos.
• ¿Cómo se deben ordenar los intervalos iguales? Use un desempate estable; cualquier recompensa óptima es aceptable.

Estructura de respuesta en 30 segundos

“Ordeno los trabajos por end y defino dp[i] como la mejor recompensa de los primeros i trabajos. Para el trabajo i, busco de forma binaria el último trabajo cuyo fin sea a lo sumo start[i]; llamo a su tamaño de prefijo compatible p. La recurrencia es dp[i] = max(dp[i-1], reward[i] + dp[p]): omitir el trabajo o tomarlo con su prefijo compatible. Almaceno un marcador de elección y hago backtracking para recuperar los trabajos. El ordenamiento y cada búsqueda binaria toman un tiempo de O(n log n) y los arreglos usan un espacio de O(n)”.

Respuesta detallada paso a paso

Paso 1: Explicar por qué una regla voraz es insuficiente.

La estrategia voraz por tiempo de finalización más temprano es correcta cuando todos los trabajos tienen el mismo valor. Con diferentes recompensas, un trabajo corto de bajo valor puede bloquear una combinación mejor, por lo que el tiempo de finalización local o la recompensa local no son suficientes.

Paso 2: Definir el estado ordenado.

Después de ordenar, sea dp[i] el óptimo para los trabajos 0..i-1, con dp[0] = 0. Omitir el trabajo i-1 da inmediatamente dp[i-1].

Paso 3: Calcular el predecesor.

Para el trabajo i-1, encuentre el mayor j < i-1 con end[j] <= start[i-1]. Realice una búsqueda binaria en los tiempos de fin ordenados y devuelva su tamaño de prefijo compatible p; tomar el trabajo produce reward[i-1] + dp[p].

Paso 4: Escribir la recurrencia y la reconstrucción.

dp[0] = 0
for i = 1..n:
  skip = dp[i - 1]
  take = reward[i - 1] + dp[p(i - 1)]
  dp[i] = max(skip, take)
  chose[i] = take > skip

Haga backtracking desde i = n: si chose[i] es verdadero, registre el trabajo i-1 y salte a p(i-1); de lo contrario, decremente i. Invierta la lista recopilada. Fije un desempate cuando las dos recompensas sean iguales.

Paso 5: Demostrar la corrección.

Cualquier óptimo sobre los primeros i trabajos excluye el trabajo i-1, rindiendo a lo sumo dp[i-1], o lo incluye. En este último caso, todos los demás trabajos se encuentran en los primeros p(i-1) trabajos compatibles, rindiendo a lo sumo reward[i-1] + dp[p(i-1)]. La recurrencia toma el mayor de estos casos exhaustivos. Con el caso base dp[0] = 0, la inducción demuestra que cada estado es óptimo.

Paso 6: Proteger los límites de implementación.

La búsqueda de predecesores debe usar <= para que los trabajos adyacentes sigan siendo compatibles. Comience desde cero para admitir recompensas negativas y el conjunto vacío. Invierta el resultado del backtracking porque la reconstrucción se ejecuta desde el final.

Paso 7: Analizar la complejidad.

El ordenamiento cuesta O(n log n), y una búsqueda binaria por trabajo también cuesta O(n log n) en total. Los arreglos de programación dinámica, predecesores y elecciones usan un espacio de O(n). Indique el tamaño de la salida por separado si se contabiliza.

Paso 8: Identificar alternativas.

Si los tiempos de finalización son enteros acotados pequeños, un escaneo indexado por tiempo puede evitar el ordenamiento por comparación. Si las recompensas son iguales, la estrategia voraz por finalización más temprana es suficiente. Un límite de a lo sumo k trabajos o múltiples recursos agrega dimensiones de estado y requiere una nueva recurrencia.

Respuesta de muestra de alta calidad

“Ordeno por tiempo de finalización y defino dp[i] como la recompensa máxima entre los primeros i trabajos. Para cada trabajo, busco de forma binaria el último predecesor con end <= start. Omitir da dp[i-1]; tomar da reward[i] + dp[p(i)], por lo que mantengo el valor mayor y registro la elección para el backtracking. La demostración divide cada óptimo según si contiene el trabajo actual; si lo hace, los trabajos restantes deben provenir del prefijo compatible. El ordenamiento y la búsqueda binaria toman un tiempo de O(n log n) y un espacio auxiliar de O(n). Pruebo trabajos adyacentes, tiempos de finalización iguales, recompensas negativas, superposición completa y entrada vacía”.

Errores comunes

• Estrategia voraz por mayor recompensa → un trabajo puede bloquear una combinación de mayor suma → compare tomar y omitir con DP.
• Tratar el fin/inicio igual como un conflicto → los trabajos adyacentes válidos desaparecen → use end <= start.
• Ordenar solo por inicio → dp[i-1] ya no describe un prefijo estable → ordene por fin.
• Escaneos lineales de predecesores → el tiempo total se convierte en O(n²) → haga búsqueda binaria en los tiempos de fin.
• Inicializar desde la primera recompensa → una entrada con todos los valores negativos no puede elegir el conjunto vacío → establezca dp[0] = 0.
• Olvidar invertir el backtracking → los trabajos seleccionados se devuelven al revés → invierta después de la recolección.
• Dejar los empates de igual recompensa sin especificar → la salida cambia entre ejecuciones → fije un desempate.
• Afirmar que una dimensión maneja límites de recursos → las restricciones adicionales no están representadas → agregue dimensiones o remodele.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué es segura la regla de límites iguales?

Si un trabajo termina exactamente cuando otro comienza, no se superponen según la convención establecida. Por lo tanto, la prueba de predecesor debe incluir la igualdad; cambiarla a < resuelve un problema diferente.

Pregunta de seguimiento 2: ¿Puede ser esto siempre O(n)?

Con tiempos enteros acotados pequeños, el escaneo directo de tiempo puede ser lineal. En el modelo de comparación general, el ordenamiento en sí cuesta O(n log n), así que no prometa tiempo lineal incondicionalmente.

Pregunta de seguimiento 3: ¿Cómo se reconstruyen los trabajos?

Almacene un bit de elección o un puntero al padre. Desde i = n, tome el trabajo actual y salte a su predecesor, o decremente al omitir; invierta los trabajos recopilados.

Pregunta de seguimiento 4: ¿Qué sucede si se pueden seleccionar a lo sumo k trabajos?

Agregue una dimensión de conteo como dp[i][c] para la mejor recompensa usando c trabajos entre los primeros i. El tiempo y el espacio aumentan en consecuencia.

Pregunta de seguimiento 5: ¿Qué sucede si la recompensa depende de los trabajos adyacentes?

La suposición de recompensa independiente ya no se sostiene. Incluya la adyacencia en el estado o modélela como un costo de transición; la recurrencia original no se justifica sin ese cambio.

Pregunta de seguimiento 6: ¿Qué sucede si todos los trabajos tienen el mismo tiempo de finalización?

El ordenamiento estable es suficiente. Sus predecesores suelen ser idénticos y la recurrencia aún compara cada candidato. Para intervalos idénticos, solo importa la mejor recompensa.

Pregunta de seguimiento 7: ¿Cuándo es correcto el enfoque voraz?

Cuando todas las recompensas son iguales y el objetivo es seleccionar el mayor número de trabajos, la estrategia voraz por finalización más temprana tiene un argumento de intercambio. Con recompensas desiguales, use programación dinámica ponderada.