## 2018年12月26日水曜日

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

コード(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()
```

```\$ ./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
__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.
\$
```