[Python] Algorithm-aware code

Algorithm-aware Python code

problem

You will be given a timetable for classes at a school.
Only one lesson can be held at the same time in one classroom.
Implement a program that asks how many classrooms your school needs.
[(Start time,ending time), ...]

In addition, it should be noted"Solution ①"The processing speed should be faster than the implementation of.

INPUT/OUTPUT

#example
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'processing speed: {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')


#Check processing speed
solution(classes)

Answer

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

#Check processing speed
solution2(classes)

Reference Youtube

Recommended Posts

[Python] Algorithm-aware code
python character code
Python code acceleration approach
Rewrite Python2 code to Python3 (2to3)
infomap python draw code
Before writing Python code
About Python3 character code
Python Requests status code
OpenCV basic code (python)
Get country code with python
Python with VS Code (Windows 10)
Python
Python code memo for yourself
[Python] Frequently used library code
Debug Python with VS Code
2.x, 3.x character code of python
Stop Omxplayer from Python code
Python frequently used code snippets
Generate QR code in Python
[Python] Sample code for Python grammar
Character code learned in Python
Convert python 3.x code to python 2.x
Document Python code with Doxygen
That Python code has no classes ...
Automatically format Python code in Vim
[Code] Module and Python version output
Write selenium test code in python
Execute Python code from C # GUI
Check python code styles using pep8
[Python] Read the Flask source code
Code tests around time in Python
[VS Code] ~ Tips when using python ~
Install python with mac vs code
Installation of Visual studio code and installation of python
kafka python
Fourier series verification code written in Python
Python basics ⑤
python + lottery 6
Python Summary
Built-in python
Python comprehension
Studying python
Python 2.7 Countdown
Python memorandum
Python FlowFishMaster
Python service
Execute Python code on C ++ (using Boost.Python)
python tips
Python memo
Python comprehension
python> link> strftime () and strptime () behavior / code
Python Singleton
Write test-driven FizzBuzz code using Python doctest.
Python basics ④
Python Memorandum 2
Python increment
atCoder 173 Python
[Python] function
Python installation
Getting Python source code metrics using radon
python tips