任务调度

[编程题]任务调度

热度指数：1459 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

读入任务调度序列，输出n个任务适合的一种调度方式。

输入描述:

输入包含多组测试数据。

每组第一行输入一个整数n（n<100000），表示有n个任务。

接下来n行，每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后继任务。

输出描述:

输出调度方式，输出如果有多种适合的调度方式，请输出字典序最小的一种。

示例1

输入

4
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)

输出

Task0 Task1 Task2 Task3

算法知识视频讲解

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        list1=[]
        for i in range(n):
            index=input().strip()
            index1=[]
            for j in range(len(index)):
                if index[j]=='(' or index[j]==')':
                    index1.append(',')
                else:
                    index1.append(index[j])
            #print(''.join(index1[:-1]))
            list1.append((''.join(index1[:-1])).split(','))
        #print(list1)
        dict1={}
        for i in list1:
            if i[1:]==['NULL']:
                dict1[i[0]]=['u']
            else:
                dict1[i[0]]=sorted(i[1:])
        #print(dict1)
        dict1=sorted(dict1.items(),key=lambda x:(x[1],x[0]))
        result=[]
        for i in dict1:
            result.append(i[0])
        print(' '.join(result))
    except:
        break
参考大佬的方案，字典再加两重排序

编辑于 2019-08-05 10:20:56 回复(0)

Python

TimeMac

人生苦短

res = []
for _ in range(int(input())):
    task = input()[:-1].replace('NULL', 'u').split('(')  #-1去掉右括号,把NULL替换成u（比'Task'大就好），排序会靠后
    res.append([task[0], sorted(task[1].split(','))])   #将后序任务也进行排序
res.sort(key=lambda x: (x[1], x[0]))           #以后序任务为首要，再以前序任务为次要排序
print(" ".join(i[0] for i in res))

编辑于 2019-02-28 13:32:26 回复(0)