启动多任务排序

• A任务依赖B任务，执行时需要先执行B任务，完成后才可以执行A任务；
• 若一个任务不依赖其他任务，则可以立即执行，多个同时执行的任务按照字母顺序A-Z排序；
• 若B依赖A，C依赖A，D依赖B、C、E，则任务执行顺序为A、E、B、C、D；AE是同时执行且按照字母顺序；
  输入描述：
  多个任务的依赖关系；如A->B A依赖B，多组依赖关系用空格隔开
  输出描述：
  任务执行顺序，多个任务用空格隔开

示例1
输入：
A->B C->B
输出：
B A C

示例2
输入：
B->A C->A D->B D->C D->E
输出：
A E B C D

示例3
输入：
B->A E->A D->A E->D C->B F->B
输出：
A B D C E F

思路：

• 迭代处理依赖关系列表，当没有依赖关系时（列表为空），所有的任务可以同时执行，只需按照字母顺序排序即可；
• 每个依赖关系字符串使用 ‘->’ 分割出主动依赖的任务，被依赖的任务
  • 主动依赖的任务放入一个集合depending_tasks；
  • 被动依赖的任务放入一个集合depended_tasks；
  • 两个集合的并集为所有的任务（all_tasks 集合）；
  • 两个集合的差集（depended_tasks - depending_tasks）为独立的任务，独立的任务可以立即执行，并按照字母顺序排序；
• 将可以立即执行的任务排序后放入task_run_order列表，并重新过滤依赖关系列表（若依赖的任务已经执行，则删除该依赖关系）
• 继续迭代处理剩余的依赖关系列表，直至其为空，此时剩余的任务（all_tasks - task_run_order）不再有依赖关系，可以同时执行，并按照字母顺序排序即可，最后加入task_run_order列表。
• 返回task_run_order

python"># __author__ = "laufing"
from typing import List


class SortTask:
    def solution(self, dependent_relations: List[str]):
        # 迭代
        task_run_order = []
        # 所有的任务
        all_tasks = set()

        while dependent_relations:
            # 主动依赖其他任务的任务
            depending_tasks = set()
            # 被依赖的任务
            depended_tasks = set()
            for relation in dependent_relations:
                # 任务分割 前者主动依赖  后者被动依赖
                task_a, task_b = relation.split("->")

                if task_a not in depending_tasks:
                    depending_tasks.add(task_a)
                if task_b not in depended_tasks:
                    depended_tasks.add(task_b)

            print("depending:", depending_tasks)
            print("depended:", depended_tasks)
            if not all_tasks:
                all_tasks = depending_tasks | depended_tasks

            # 获取不依赖其他任务的 任务(独立的)
            # 独立的任务可以立即执行（注意按字母顺序排序）
            independent_tasks = depended_tasks - depending_tasks
            task_run_order.extend(sorted(list(independent_tasks)))
            dependent_relations = list(filter(lambda i: i[-1] not in task_run_order, dependent_relations))

        # 依赖关系解决完后，执行剩余的任务
        task_run_order.extend(sorted(list(all_tasks - set(task_run_order))))

        return task_run_order


if __name__ == '__main__':
    sort_task = SortTask()
    while True:
        try:
            # 输入
            lay_relations = input("lay:").strip().split()
            print("origin relations:", lay_relations)
            # 解决方案
            result = sort_task.solution(lay_relations)
            # 输出结果
            print(" ".join(result))
        except KeyboardInterrupt:
            break