Жадные алгоритмы

определение
Алгоритмическая парадигма, которая создает решение по частям, всегда выбирая часть, которая предлагает наиболее очевидную и непосредственную выгоду. Жадные алгоритмы используются для задач оптимизации.

Задачу оптимизации можно решить с помощью Жадного алгоритма, если задача обладает следующим свойством: На каждом шаге можно сделать выбор, который выглядит лучше всего в данный момент, и получить оптимальное решение полной задачи .
Задача
Задано n действий с указанием времени их начала и окончания. Выберите максимальное количество действий, которые может выполнять один человек, предполагая, что человек может работать только над одним действием одновременно. действия представлены в виде неотсортированного словаря

Жадный выбор состоит в том, чтобы всегда выбирать следующее действие, время окончания которого наименьшее среди оставшихся действий, а время начала больше или равно времени окончания ранее выбранного действия. Мы можем сортировать действия по времени их окончания, чтобы всегда рассматривать следующее действие как действие с минимальным временем окончания.

from collections import OrderedDict


def printMaxActivities(actions: dict) -> None:

    acn = sorted(actions, key=actions.get(1))
    ord_actions = OrderedDict()
    for k in acn:
        ord_actions[k] = actions[k]

    i = acn[0]
    print(i, end=' ')
    for j in ord_actions:
        if ord_actions[j][0] >= ord_actions[i][1]:
            print(j, end=' ')
            i = j


if __name__ == '__main__':
    actions: dict = {
        'action2': [3, 4],
        'action3': [0, 6],
        'action5': [8, 9],
        'action6': [5, 9],
        'action1': [1, 2],
        'action4': [5, 7],
    }
    printMaxActivities(actions)