[Python] Code, der Algorithmen kennt

Algorithmusbewusster Python-Code

Problem

Sie erhalten einen Stundenplan für den Unterricht an einer Schule.
Bis zu eine Klasse kann gleichzeitig in einem Klassenzimmer abgehalten werden.
Implementieren Sie ein Programm, das fragt, wie viele Klassenräume Ihre Schule mindestens benötigt.
[(Startzeit,Endzeit), ...]

Darüber hinaus sollte beachtet werden"Lösung ①"Die Verarbeitungsgeschwindigkeit sollte schneller sein als die Implementierung von.

INPUT/OUTPUT

#Beispiel
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),
]

Lösung ①

def dec_speed(func):
    def wraps(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f'Verarbeitungsgeschwindigkeit: {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')


#Verarbeitungsgeschwindigkeit prüfen
solution(classes)

Antworten

@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')

#Verarbeitungsgeschwindigkeit prüfen
solution2(classes)

Referenz Youtube

Recommended Posts

[Python] Code, der Algorithmen kennt
Python-Zeichencode
Schreiben Sie Python2-Code in Python3 um (2to3)
Infomap Python-Zeichencode
Vor dem Schreiben von Python-Code
Python Fordert den Statuscode an
Holen Sie sich den Ländercode mit Python
Python mit VSCode (Windows 10)
Python
Persönliches Python-Code-Memo
Debuggen Sie Python mit VS-Code
2.x, 3.x Serienzeichencode von Python
Stoppen Sie Omxplayer vom Python-Code
Python verwendete häufig Codefragmente
Generieren Sie QR-Code in Python
[Python] Beispielcode für die Python-Grammatik
In Python gelernter Zeichencode
Konvertieren Sie Python 3.x-Code in Python 2.x.
Dokumentieren Sie Python-Code mit Doxygen
Dieser Python-Code hat keine Klassen ...
Formatieren Sie Python-Code automatisch mit Vim
Schreiben Sie Selentestcode in Python
Führen Sie Python-Code über die C # -GUI aus
Überprüfen Sie den Python-Codestil mit pep8
[Python] Lesen Sie den Flask-Quellcode
Code-Tests rund um die Uhr in Python
Installieren Sie Python mit Mac vs Code
Installation von Visual Studio Code und Installation von Python
Kafka Python
In Python geschriebener Fourier-Serien-Verifizierungscode
Python-Grundlagen ⑤
Python-Zusammenfassung
Eingebaute Python
Python-Einschlussnotation
Python studieren
Python 2.7 Countdown
Python-Memorandum
Python FlowFishMaster
Python-Dienst
Führen Sie Python-Code unter C ++ aus (mit Boost.Python).
Python-Tipps
Python-Memo
Python-Einschlussnotation
Python> Link> Verhalten / Code von Strftime () und strptime ()
Python Singleton
Schreiben Sie testgetriebenen FizzBuzz-Code mit Python doctest.
Python-Grundlagen ④
Python-Memorandum 2
Python-Inkrement
atCoder 173 Python
[Python] -Funktion
Python-Installation
Holen Sie sich Python-Quellcode-Metriken mit Radon