second_task.py

from itertools import count, takewhile, accumulate
import operator
from pprint import pprint


def to_task_name(n):
    return chr(ord('A') + n)


def create_tasks_iter(first_time, last_time):
    return map(create_task, zip(map(to_task_name, count()), first_time, last_time))


def create_task(t):
    return {
        'name': t[0],
        'first_time': t[1],
        'last_time': t[2]
    }


def sorted_with_cmp(iterable, cmp):
    lst = list(iterable)
    res = []

    for a in lst:
        i = len(list(takewhile(lambda b: cmp(a, b) < 0, res)))
        res = res[:i] + [a] + res[i:]

    return res


def compare_tasks(a, b):
    return min(a['first_time'], b['last_time']) - min(a['last_time'], b['first_time'])


def get_ordered_tasks_iter(first_time, last_time):
    tasks = create_tasks_iter(first_time, last_time)
    return reversed(sorted_with_cmp(tasks, compare_tasks))


def get_all_time(ordered_tasks):
    return ordered_tasks[0]['first_time'] + sum(map(operator.itemgetter('last_time'), ordered_tasks))


def run_test_1():
    first_time = [6, 3, 2, 5, 4, 8, 7]
    last_time = [5, 7, 6, 8, 4, 3, 2]
    ordered_tasks = list(get_ordered_tasks_iter(first_time, last_time))
    all_time = get_all_time(ordered_tasks)
    assert 37 == all_time, 'Expected {}, got {}'.format(37, all_time)


def get_time_lines(ordered_tasks):
    first_stage = list(map(operator.itemgetter('first_time'), ordered_tasks))
    last_stage = map(operator.itemgetter('last_time'), ordered_tasks)
    return {
        'first_stage': [0] + list(accumulate(first_stage)),
        'last_stage': [first_stage[0]] + list(map(lambda x: x + first_stage[0], accumulate(last_stage)))
    }


def create_task_on_time_line(tpl):
    return [
        ('name', tpl[0]['name']),
        ('starts', tpl[1]),
        ('ends', tpl[2])
    ]


def get_tasks_on_time_line_iter(ordered_tasks, time_line):
    return map(create_task_on_time_line, zip(ordered_tasks, time_line, time_line[1:]))


def run_test_2():
    first_time = [6, 7, 4, 2, 3, 5, 8]
    last_time = [8, 3, 7, 4, 2, 5, 6]
    ordered_tasks = list(get_ordered_tasks_iter(first_time, last_time))
    all_time = get_all_time(ordered_tasks)
    pprint(ordered_tasks)
    time_lines = get_time_lines(ordered_tasks)
    pprint(time_lines)
    pprint(list(get_tasks_on_time_line_iter(ordered_tasks, time_lines['first_stage'])))
    pprint(list(get_tasks_on_time_line_iter(ordered_tasks, time_lines['last_stage'])))
    assert 37 == all_time, 'Expected {}, got {}'.format(37, all_time)


def main():
    for i, t in enumerate((run_test_1, run_test_2)):
        t()
        print('Test #{} passed'.format(i + 1))

    first_time = map(int, input('Enter first time for each task: ').split())
    last_time = map(int, input('Enter last time for each task: ').split())
    tasks = list(create_tasks_iter(first_time, last_time))
    ordered_tasks = list(reversed(sorted_with_cmp(tasks, compare_tasks)))

    pprint(ordered_tasks)
    print(ordered_tasks[0]['first_time'] + sum(map(operator.itemgetter('last_time'), ordered_tasks)))


if __name__ == '__main__':
    main()