求大神讨论Facebook 面经经典难题

希望有大神可以一起讨论一下这几个题：
Question1:

这个稍微难， 说有一堆task，每个有不同时间完成， 然后有一堆worker， 说如何分配 task to worker，完成时间最短， task是独立的。.看起来像背包， DP

task：  2，2，3，7， 1

worker： 2

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

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

上过一个算法课，大概思路就是做一个二维的meeting room II。 扫描线算法。

谢谢大神们

Question 3: If this is treated as 2D meeting room II problem, I am thinking for any fix x, solve a 1-D Meeting Room II. For each 1-D problem, because I need to filter out those rectangles which don't intersect x, I can only do O(N*logN) for each 1-D problem. Total O(N^2*logN). Anyone has O(N^2) solution?

1. struct Rect {
   
2.   int x1, x2, y1, y2;
   
3. };
   
4. 
   
5. int maxOverlap1D(vector<Rect>& rects, int x) {
   
6.   map<int, int> count;
   
7.   for (auto& r : rects) {
   
8.     if (x < r.x1 || x > r.x2) continue;
   
9.     count[r.y1]++, count[r.y2 + 1]--;
   
10.   }
    
11. 
    
12.   int res = 0, total = 0;
    
13.   for (auto& p : count)
    
14.     res = max(res, total += p.second);
    
15.   return res;
    
16. }
    
17. 
    
18. int maxOverlap2D(vector<Rect>& rects) {
    
19.   int res = 0;
    
20.   for (auto& r : rects)
    
21.     res = max(res, maxOverlap1D(rects, r.x1));
    
22.   return res;
    
23. }
    

复制代码

大神，可以用greedy吗？task从高到低排个序，然后用一个min heap, 每次把work load最小的worker弹出来，把当前最大的task分配给他。

补充内容 (2017-4-24 16:02):
我是说第一题

say543 发表于 2017-3-30 14:31
看不太懂 你怎么用一维限制只找三个.....

一维数组实现二维DP嘛，本来二维表就是一行一行挨个写下来的

这个二维表的行是假设有nn个subarray, nn就是  行index+1

DP(nn, i) = Max(DP(nn-1, i-k)+sum(i-k, i), DP(nn, i-1))
这个是状态转移方程， DP是有subarray的个数下，从0到i的最大值。sum(i-k, i)是元素从i-k到i的累加和
状态转移方程的体现在第13行

这个代码是测试过的，应该没大问题，我发之前应该写注释的

补充内容 (2017-3-30 15:43):
DP是有subarray的个数下
=>DP是有nn个subarray的个数下

第二题因该就是dp[k][n] k =3, n 是以n为结尾of 最后一个seq 加上前面两个seq 的总和 求越大越好 o(n) 没问题

补充内容 (2017-2-19 14:35):

错了这样好像是o(nk) 楼主怎做到o(n)的?

第一轮 只会dfs 暴力解 楼主怎转成背包问题?

第三轮 我有在某家面经看过 但是是圆形 但是一职没想出怎么用线段扫描法 楼主能说说吗?

Question 1 我有点思路。看下有道理没
就是如果我限制三个worder的task上限，那么就变成了一个多背包问题。
多背包问题可以用背包问题再多一维解出来。

这里找了一篇神文，求解多背包的
http://www.or.deis.unibo.it/kp/Chapter6.pdf

然后不断提升这个上限，直到刚刚好装满所有task。
(也可以二分搜索法)
这个上限就是最短时间。

翻滚吧豆子 发表于 2017-2-27 13:45
Question 1 我有点思路。看下有道理没
就是如果我限制三个worder的task上限，那么就变成了一个多背包问题 ...

BST 上限是可行的 但是问题在于 DP 的worker 是不定的 这要怎么dp呢? 感觉跟多重背包不大依样?

say543 发表于 2017-2-19 14:30
第二题因该就是dp[k][n] k =3, n 是以n为结尾of 最后一个seq 加上前面两个seq 的总和 求越大越好 o(n) 没问 ...

如果是M个subarray(M = 3在此题), 那么用DP的话能实现O(MN)的，N是Array总长度。

shevchenko777 发表于 2017-3-30 06:46
如果是M个subarray(M = 3在此题), 那么用DP的话能实现O(MN)的，N是Array总长度。

是的，这道题和股票IV很像

1.   public static int findNWindow(int[] nums, int k, int n){
   
2.     int[] lastMaxK = new int[nums.length];
   
3.     int[] maxK = new int[nums.length];
   
4.    
   
5.     for(int nn=0; nn<n; nn++){
   
6.       int curSum=0;
   
7.       for(int i=nn*k; i<nums.length; i++){
   
8.         curSum += nums[i];
   
9. 
   
10.         if(i==(nn+1)*k-1) maxK[i] = curSum;
    
11.         if(i>=(nn+1)*k){
    
12.           curSum -= nums[i-k];
    
13.           maxK[i] = Math.max(lastMaxK[i-k] + curSum, maxK[i-1]);
    
14.         }
    
15.       }
    
16.       int[] t = lastMaxK;
    
17.       lastMaxK = maxK;
    
18.       maxK = t;
    
19.     }
    
20.    
    
21.     return lastMaxK[maxK.length-1];
    
22.   }

复制代码

关注一下

翻滚吧豆子 发表于 2017-3-30 07:48
是的，这道题和股票IV很像

看不太懂 你怎么用一维限制只找三个.....