狗家店面跪经

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

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

没怎么好好刷题就随便说了个brute force。。应该是跪了

这题我想了几天，发现不复杂。根本就不需要拓扑排序。解法有点像BFS。

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

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

补充内容 (2019-6-23 12:00):
我这里用的方法是:
先做完的server取最长的task.

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维护

楼主面的是美国的全职吗？现在还在发面试吗？

Akira明明 发表于 2019-3-25 06:04
楼主面的是美国的全职吗？现在还在发面试吗？

因为有事拖到现在才面的，二月底发的面试通知

这个感觉有点麻烦，lz最后怎么解的啊

店面遇到这个题应该算是比较背的，这题还挺麻烦，我觉得应该是用拓扑排序，先找indegree为0的点放进线程池子，等结束在找下一波indegree为0的点，直到最后算出时间。

yangyuzhiguang 发表于 2019-3-25 06:39
店面遇到这个题应该算是比较背的，这题还挺麻烦，我觉得应该是用拓扑排序，先找indegree为0的点放进线程池 ...

我也是这样的想法。但是隐约觉得得到的不一定是最优解

先找critical path , schedule 第一段 并且设置成0， 再重新计算critial path, schedule 下一个。
这样貌似能最优，复杂度有点高

您好！
本帖隐藏的内容需要积分高于 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

店面这难度也太过分了