Super Computer – solution CodinGame en Python
Super Computer est le problème classique d'ordonnancement d'intervalles : chaque demande devient un intervalle semi-ouvert [J, J+D), on trie par jour de fin, puis on parcourt la liste une fois en acceptant toute demande qui commence au plus tôt à la fin de la dernière acceptée. Le nombre de demandes retenues est la réponse, et le choix glouton « fin la plus précoce d'abord » est démontré optimal. Le tri domine : O(n log n).
L'énoncé
Un laboratoire dispose d'un seul supercalculateur et reçoit N demandes de réservation. Chaque demande commence le jour J et dure D jours consécutifs, donc occupe les jours J à J+D-1. Deux demandes ne peuvent pas partager un jour. Il faut afficher le nombre maximal de demandes que l'on peut accepter ensemble.
N peut atteindre environ 100 000, les jours de début montent vers le million et les durées vers le millier de jours : tout ce qui est quadratique en N, ou qui parcourt chaque jour de chaque demande dans un langage lent, risque le dépassement de temps sur les plus gros tests.
La démarche, étape par étape
- Représenter chaque demande par un intervalle semi-ouvertOn stocke une demande sous la forme (début, fin) avec fin = J + D. La borne de fin exclusive supprime toute question de décalage d'une unité : une demande qui finit à 10 et une autre qui commence à 10 ne se chevauchent pas, puisque le dernier jour de la première est 9.
- Trier par jour de finOn trie tous les intervalles selon leur fin. Les égalités et l'ordre des débuts n'ont aucune incidence sur la justesse : seul le jour de fin pilote le choix glouton.
- Parcours glouton avec une seule variableOn garde libre_a_partir_de, le premier jour où la machine est libre (0 au départ). Pour chaque intervalle dans l'ordre trié, on l'accepte si début >= libre_a_partir_de et on met libre_a_partir_de = fin. Sinon on le saute.
- Pourquoi la fin la plus précoce est optimalePrenez un planning optimal quelconque et comparez-le au glouton. Le premier choix glouton se termine au plus tard en même temps que le premier choix optimal, donc on peut l'y substituer sans créer de conflit ; en répétant l'argument demande après demande, le glouton n'accepte jamais moins de demandes.
- Afficher le compteurLe nombre d'intervalles acceptés est la réponse. Il n'est jamais nécessaire de savoir quelles demandes ont été retenues.
Complexité
O(n log n)O(n)Le tri domine ; le parcours est un simple passage linéaire. La mémoire contient la liste des intervalles et rien qui dépende de la taille du calendrier.
Code de la solution
Super Computer – Python
import sys
def main():
data = sys.stdin.read().split()
n = int(data[0])
jobs = []
for i in range(n):
start = int(data[1 + 2 * i])
duration = int(data[2 + 2 * i])
# half-open interval [start, start + duration)
jobs.append((start + duration, start))
# earliest end first
jobs.sort()
count = 0
free_from = 0 # first day the machine is free
for end, start in jobs:
if start >= free_from:
count += 1
free_from = end
print(count)
main()
Erreurs fréquentes
- Trier par jour de début ou par duréeTrier par début retient une longue demande précoce qui en bloque beaucoup de courtes ; trier par durée échoue quand une demande courte chevauche deux demandes plus longues compatibles entre elles. Seul le tri par jour de fin garantit l'optimum.
- Décalage d'une unité sur le jour de finSi vous stockez le dernier jour inclus J+D-1, le test de compatibilité doit être début > dernier_jour, pas >=. Mélanger les deux conventions accepte des demandes qui se chevauchent ou rejette celles qui se touchent, et le résultat dérive de quelques unités sur les gros tests.
- Marquer chaque jour de chaque demandeUn calendrier de booléens passe en C mais devient lent en Python ou en JavaScript, car la longueur cumulée des demandes peut atteindre environ 10^8 jours. La seule variable libre_a_partir_de rend le calendrier inutile.
- Lecture d'entrée lenteAvec 100 000 lignes, appeler input() par ligne passe en général, mais tout lire d'un coup avec sys.stdin.read().split() supprime tout risque sur le plus gros test.
Pour aller plus loin
Le puzzle est souvent présenté comme « Earliest Deadline First », mais le mot deadline induit en erreur : il n'y a aucune échéance ici, seulement des intervalles fixes, et le bon nom est le problème de sélection d'activités. Une façon élégante de se convaincre de l'optimalité du glouton est l'argument « il reste en avance » : après k choix, la k-ième demande acceptée par le glouton se termine toujours au plus tard en même temps que la k-ième d'un planning valide quelconque. Si un planning optimal avait une demande de plus, celle-ci commencerait après la k-ième fin optimale, donc après la k-ième fin gloutonne, et le glouton l'aurait acceptée. Cela montre aussi que les égalités de jour de fin peuvent être départagées n'importe comment.
Questions fréquentes
Super Computer est-il un problème de programmation dynamique ?
Non. L'ordonnancement d'intervalles pondéré demande de la PD, mais ici chaque demande compte autant, donc la stratégie gloutonne par fin la plus précoce est optimale et bien plus simple.
Deux demandes se chevauchent-elles si l'une finit le jour 5 et la suivante commence le jour 5 ?
Oui. Une demande qui commence le jour J avec une durée D occupe le jour J+D-1 en dernier, donc la suivante peut commencer au plus tôt le jour J+D. Avec des intervalles semi-ouverts, le test se résume à début >= fin précédente.
Pourquoi ma solution dépasse-t-elle le temps sur le dernier test ?
En général parce qu'elle compare toutes les paires de demandes ou remplit un tableau jour par jour dans un langage lent. Un seul tri puis un seul parcours traitent 100 000 demandes instantanément.