狗家店面跪经

看大家讨论，感觉这题好难

lalxyy 发表于 2019-3-25 09:53
我也是这样的想法。但是隐约觉得得到的不一定是最优解

肯定有问题，因为你这个取舍完全没考虑到后面的进行情况，反🍐很容易举出来

这题可以拆分成两部分。第一部分是拓扑排序。alien dictionary, 得到一个任务列表之后，题目转成用k的cpu需要多久完成任务。附上代码和测试用例

1. def schedule(graph, times, k):
   
2.     from collections import defaultdict
   
3.     ind = defaultdict(set)
   
4.     oud = defaultdict(set)
   
5.     nodes = set()
   
6.     for a, b in graph:
   
7.         oud[a].add(b)
   
8.         ind[b].add(a)
   
9.         nodes.add(a)
   
10.         nodes.add(b)
    
11. 
    
12.     import heapq
    
13.     leaves = [i for i in nodes if not ind[i]]
    
14. 
    
15.     ans = []
    
16.     # 对同时可以执行的任务也有顺序要求，这里用heap代替list
    
17.     heapq.heapify(leaves)
    
18.     while leaves:
    
19.         leaf = heapq.heappop(leaves)
    
20.         ans.append(leaf)
    
21.         for nei in oud[leaf]:
    
22.             ind[nei].remove(leaf)
    
23.             if not ind[nei]:
    
24.                 heapq.heappush(leaves, nei)
    
25. 
    
26.     # 计算ans所需要的时间，维护一个大小为k的heap,heap内存的是任务结束时间
    
27.     pq = []
    
28.     cur = 0 # 当前时间
    
29.     for i in ans:
    
30.         heapq.heappush(pq, times[i] + cur)
    
31.         if len(pq) == k:
    
32.             cur = heapq.heappop(pq)
    
33.     cur = max(pq)
    
34.     return cur
    
35. 
    
36. print(schedule([[3,1],[3,2], [1,0]], [1,2,3,4], 2))

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

拓扑排序够了啊，因为题目中说到：
用工作的index来break tie，比如task 1和task 2 都可以被执行了，但只有一个available processor，就只能先做task 1

补充内容 (2019-3-29 09:39):
哦，还有工作时间，貌似不是那么简单的事情。

每个task做完的时间还不一样？这也太难了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

chenchen628 发表于 2019-3-29 16:44
1. 拓扑排序，确定每个任务现在开始最少还要多久。同时记录每个任务的前置数量，以及可能unlock哪些。 2.  ...

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.   int fastedTaskSchedule(int N, vector<int>& tasks, vector<vector<int>>& prerequisites, int machines) {
   
10.     vector<int> pre_nums(N, 0);
    
11.     vector<vector<int>> unlocks(N, vector<int>());
    
12.     for (auto pre : prerequisites) {
    
13.       pre_nums[pre[1]] ++;
    
14.       unlocks[pre[0]].push_back(pre[1]);
    
15.     }
    
16.         
    
17.     vector<int> time_left(N, -1);
    
18.     for (int i = 0; i < N; ++i) {
    
19.       if (pre_nums[i] == 0) getTimeLeft(i, tasks, unlocks, time_left);
    
20.     }
    
21.         
    
22.     auto cmp_min = [](const pair<int, int>& t1, const pair<int, int>& t2) {
    
23.       return t1.second > t2.second;
    
24.     };
    
25.     auto cmp_max = [](const pair<int, int>& t1, const pair<int, int>& t2) {
    
26.       return t1.second < t2.second;
    
27.     };
    
28.         
    
29.     priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp_min)> task_finish(cmp_min);
    
30.     priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp_max)> task_ready(cmp_max);
    
31.         
    
32.     for (int i = 0; i < N; ++i) {
    
33.       if (pre_nums[i] == 0) task_ready.push({i, time_left[i]});
    
34.     }
    
35.         
    
36.     int cur_time = 0;
    
37.     while (!task_ready.empty() || !task_finish.empty()) {
    
38.       while (task_finish.size() < machines && !task_ready.empty()) {
    
39.         auto task = task_ready.top();
    
40.         task_ready.pop();
    
41.         task_finish.push({task.first, cur_time + tasks[task.first]});
    
42.       }
    
43.             
    
44.       auto cur_finish = task_finish.top();
    
45.       task_finish.pop();
    
46.       cur_time = cur_finish.second;
    
47.       int cur = cur_finish.first;
    
48.       for (int next : unlocks[cur]) {
    
49.         pre_nums[next] --;
    
50.         if (pre_nums[next] == 0) task_ready.push({next, time_left[next]});
    
51.       }
    
52.     }
    
53.     return cur_time;
    
54.   }
    
55.    
    
56.   void getTimeLeft(int i, const vector<int>& tasks, const vector<vector<int>>& unlocks, vector<int>& time_left) {
    
57.     if (time_left[i] != -1) return;
    
58.     time_left[i] = tasks[i];
    
59.     int max_next = 0;
    
60.     for (int next : unlocks[i]) {
    
61.       getTimeLeft(next, tasks, unlocks, time_left);
    
62.       max_next = max(max_next, time_left[next]);
    
63.     }
    
64.     time_left[i] += max_next;
    
65.   }
    
66. };
    
67. 
    
68. int main()
    
69. {
    
70.   Solution s;
    
71.    
    
72.   int N = 6;
    
73.   vector<int> tasks = {10, 10, 2, 3, 100, 200};
    
74.   vector<vector<int>> prerequisites = {{0, 1}, {2, 3}, {4, 5}};
    
75.   int machines = 2;
    
76.    
    
77.   cout << s.fastedTaskSchedule(N, tasks, prerequisites, machines) << endl;
    
78. 
    
79.   return 0;
    
80. }
    

复制代码

附上一个python版本，还有楼上讨论的两个test case

1.     def task_scheduler(dependencies, k, times)
   
2. 
   
3. [code]    def task_scheduler(dependencies, k, times):
   
4.         def makeGraph(dependencies):
   
5.             graph = collections.defaultdict(list)
   
6.             for s, e in dependencies:
   
7.                 graph[s].append(e)
   
8.             return graph
   
9.         
   
10.         def computeIndegree(graph, n):
    
11.             indegree = {}
    
12.             for i in xrange(n):
    
13.                 indegree[i] = 0
    
14.             for node in graph:
    
15.                 for nei in graph[node]:
    
16.                     indegree[nei] += 1
    
17.             return indegree
    
18.         
    
19.         n = len(times)
    
20.         graph = makeGraph(dependencies)
    
21.         indegree = computeIndegree(graph, n)
    
22.         waiting = []
    
23.         process = []
    
24.         for node in indegree:
    
25.             if indegree[node] == 0:
    
26.                 heappush(waiting, (-times[node], node))
    
27.             
    
28.         while len(process) < k and waiting:
    
29.             t, task = heappop(waiting)
    
30.             heappush(process, (-t, task))
    
31.         
    
32.         while process:
    
33.             #print process
    
34.             time, task = heappop(process)
    
35.             for nei in graph[task]:
    
36.                 indegree[nei] -= 1
    
37.                 if indegree[nei] == 0:
    
38.                     heappush(waiting, (-times[nei], nei))
    
39.                     
    
40.             #print waiting
    
41.             while len(process) < k and waiting:
    
42.                 dt, task = heappop(waiting)
    
43.                 heappush(process, (time - dt, task))
    
44.         
    
45.         return time
    
46.    
    
47.     dependencies = [[3,1],[3,2],[1,0]]
    
48.     times = [1,2,3,4]
    
49.     k = 2
    
50.     print task_scheduler(dependencies, k, times)
    
51.    
    
52.     dependencies = [[0,1],[2,3],[4,5]]
    
53.     times = [10, 10, 5, 4, 100, 200]
    
54.     k = 2
    
55.     print task_scheduler(dependencies, k, times)

复制代码

补充内容 (2019-4-10 08:11):
大体就是topological sort,外加两个priority queue维护