Coding Solution

Super Computer – solution CodinGame en Python

Difficilegreedyinterval schedulingsortingMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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é

TempsO(n log n)
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome