[Python] Code conscient des algorithmes

Code Python compatible avec les algorithmes

problème

Vous recevrez un horaire des cours dans une école.
Un seul cours peut être organisé en même temps dans une classe.
Mettez en œuvre un programme qui demande au moins de combien de classes votre école a besoin.
[(Heure de début,heure de fin), ...]

De plus, il convient de noter"Solution ①"La vitesse de traitement doit être plus rapide que la mise en œuvre de.

INPUT/OUTPUT

#exemple
classes1 = [(0, 50), (50, 100)]
answer1 = 1

classes2 = [(0, 50), (50, 100), (20, 70)]
answer2 = 2

classes3 = [(10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (60, 80)]
answer3 = 3

classes4 = [(0, 50), (50, 100), (20, 70), (50, 100)]
answer4 = 3

classes5 = [(0, 20), (10, 30), (20, 40), (30, 50)]
answer5 = 2

classes = [
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
    (10, 50), (20, 30), (30, 70), (60, 100), (70, 90), (10, 50), (20, 30), (30, 70), (60, 100), (70, 90),
]

Solution ①

def dec_speed(func):
    def wraps(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f'vitesse de traitement: {end - start}')
        return result
    return wraps


def check_time_overlaps(a: tuple, b: tuple) -> bool:
    return b[0] < a[1] < b[1]


@dec_speed
def solution(classes: list) -> int:
    num_classes = len(classes)
    max_classes = 1
    for i in range(num_classes):
        rooms = 1
        for j in range(num_classes):
            if i != j:
                check = check_time_overlaps(classes[i], classes[j])
                rooms += 1 if check else 0
        max_classes = max(max_classes, rooms)
    return max_classes

assert solution(classes1) == answer1
assert solution(classes2) == answer2
assert solution(classes3) == answer3
assert solution(classes4) == answer4
assert solution(classes5) == answer5
print('OK')


#Vérifier la vitesse de traitement
solution(classes)

Répondre

@dec_speed
def solution2(classes: list) -> int:
    timeline = []
    for start, end in classes:
        timeline.extend([(start, 1), (end, -1)])
    timeline = sorted(timeline)

    max_rooms = 0
    rooms = 0
    for _, overlap in timeline:
        rooms += overlap
        max_rooms = max(max_rooms, rooms)
    return max_rooms

assert solution2(classes1) == answer1
assert solution2(classes2) == answer2
assert solution2(classes3) == answer3
assert solution2(classes4) == answer4
assert solution2(classes5) == answer5
print('OK')

#Vérifier la vitesse de traitement
solution2(classes)

Référence Youtube

Recommended Posts

[Python] Code conscient des algorithmes
code de caractère python
Réécrire le code Python2 en Python3 (2to3)
infomap code de dessin Python
Avant d'écrire du code Python
Code d'état des requêtes Python
Obtenez le code du pays avec python
Python avec VSCode (Windows 10)
Python
Mémo de code personnel Python
Déboguer Python avec VS Code
2.x, 3.x code de caractères des séries python
Arrêtez Omxplayer à partir du code Python
Extraits de code Python fréquemment utilisés
Générer du code QR en Python
[Python] Exemple de code pour la grammaire Python
Code de caractère appris en Python
Convertir le code python 3.x en python 2.x
Documenter le code Python avec Doxygen
Ce code Python n'a pas de classes ...
Formater automatiquement le code Python avec Vim
Ecrire le code de test du sélénium en python
Exécuter du code Python à partir de l'interface graphique C #
Vérifiez le style de code python à l'aide de pep8
[Python] Lire le code source de Flask
Tests de code dans le temps en Python
Installez python avec mac vs code
Installation du code Visual Studio et installation de python
python kafka
Code de vérification de la série Fourier écrit en Python
Les bases de Python ⑤
Résumé Python
Python intégré
Notation d'inclusion Python
Étudier Python
Compte à rebours Python 2.7
Mémorandum Python
Python FlowFishMaster
Service Python
Exécuter du code Python sur C ++ (en utilisant Boost.Python)
astuces python
Mémo Python
Notation d'inclusion Python
python> lien> Comportement / code de Strftime () et strptime ()
Python Singleton
Écrivez du code FizzBuzz piloté par les tests à l'aide de Python doctest.
Les bases de Python ④
Mémorandum Python 2
Incrément Python
atCoder 173 Python
[Python] fonction
Installation de Python
Obtenez des métriques de code source Python à l'aide de radon