Algorithm - Python - 貪欲は良いことだ(終了時間順ルール、最短受講時間ルール、関数引数、貪欲アルゴリズム)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の16章(貪欲は良いことだ)、練習問題(問題1)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def earliest_finish_time(courses: list) -> list:
    '''
    >>> earliest_finish_time([[8, 10], [9, 10]])
    [9, 10]
    >>> earliest_finish_time([[9, 10], [8, 10]])
    [9, 10]
    '''
    start, finish = courses[0]
    for start_tmp, finish_tmp in courses:
        if finish_tmp < finish or \
           finish_tmp == finish and (finish_tmp - start_tmp) < finish - start:
            start = start_tmp
            finish = finish_tmp
    return [start, finish]


def remove_conflicting_courses(course: list, courses: list) -> list:
    start, finish = course
    return [[start_other, finish_other]
            for start_other, finish_other in courses
            if finish <= start_other or finish_other <= start]


def execute_schedule(courses: list, selection_rule: 'func') -> list:
    '''
    >>> courses = [[8, 10], [9, 10], [10, 12], [11, 12], [12, 14], [13, 14]]
    >>> execute_schedule(courses, earliest_finish_time)
    [[9, 10], [11, 12], [13, 14]]
    '''
    selected_courses = []
    while len(courses) > 0:
        selected_course = selection_rule(courses)
        selected_courses.append(selected_course)
        courses = remove_conflicting_courses(selected_course, courses)
    return selected_courses


if __name__ == '__main__':
    import doctest
    doctest.testmod()

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample1.py -v
Trying:
    earliest_finish_time([[8, 10], [9, 10]])
Expecting:
    [9, 10]
ok
Trying:
    earliest_finish_time([[9, 10], [8, 10]])
Expecting:
    [9, 10]
ok
Trying:
    courses = [[8, 10], [9, 10], [10, 12], [11, 12], [12, 14], [13, 14]]
Expecting nothing
ok
Trying:
    execute_schedule(courses, earliest_finish_time)
Expecting:
    [[9, 10], [11, 12], [13, 14]]
ok
2 items had no tests:
    __main__
    __main__.remove_conflicting_courses
2 items passed all tests:
   2 tests in __main__.earliest_finish_time
   2 tests in __main__.execute_schedule
4 tests in 4 items.
4 passed and 0 failed.
Test passed.
$