【Python】アルゴリズムを意識したコード

アルゴリズムを意識したPythonコード

問題

ある学校の授業の時間割が与えられる。
１つの教室で同時に出来る授業は1つまで。
学校には最低いくつの教室が必要か求めるプログラムを実装せよ。
[(開始時間, 終了時間), ...]

なお、"解決①"の実装より処理速度の速い実装であること。

INPUT/OUTPUT

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

解決①

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


# 処理速度の確認
solution(classes)

回答

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

# 処理速度の確認
solution2(classes)

参考Youtube

• https://www.youtube.com/watch?v=dpL7pR5Z_wM