Google 面经

匿名者 发表于 2021-9-10 08:50
感觉可以2 pointer, 遇到都是active， 先执行小的，同时move pointer forward, 两个一个active 一个passive ...

感觉应该是这个思路

在两个指针指向active的基础上， 看谁后面的passive长   ，谁先      。不知道是否可以                                                                                                                                                                          

ghu97 发表于 2021-9-12 22:34
想到一个greedy的做法，不确定对不对，有没有test case可以试一试？
就是优先做Passive开头的任务，然后都 ...

感觉这个比较可能对

1. public static void recipe() {
   
2.     String[][] r1 = {{"3", "ACTIVE"}, {"10", "PASSIVE"}};
   
3.     String[][] r2 = {{"4", "ACTIVE"}, {"15", "PASSIVE"}};
   
4. 
   
5.     int[][] record = new int[2][2];//[[a1, p1], [a2, p2]];
   
6.     int s1 = 0, s2 = 0;
   
7.     int total = 0;
   
8.     while (s1 < r1.length && s2 < r2.length || record[0][0] > 0 || record[1][0] > 0) {
   
9.       if (record[0][0] == 0 && record[1][0] == 0) {
   
10.         while (s1 < r1.length && "ACTIVE".equals(r1[s1][1])) {
    
11.           record[0][0] += Integer.parseInt(r1[s1++][0]);
    
12.         }
    
13.         while (s1 < r1.length && "PASSIVE".equals(r1[s1][1])) {
    
14.           record[0][1] += Integer.parseInt(r1[s1++][0]);
    
15.         }
    
16. 
    
17.         while (s2 < r2.length && "ACTIVE".equals(r2[s2][1])) {
    
18.           record[1][0] += Integer.parseInt(r2[s2++][0]);
    
19.         }
    
20.         while (s2 < r2.length && "PASSIVE".equals(r2[s2][1])) {
    
21.           record[1][1] += Integer.parseInt(r2[s2++][0]);
    
22.         }
    
23.       }
    
24. 
    
25.       System.out.println(record[0][0]+","+record[0][1]);
    
26.       System.out.println(record[1][0]+","+record[1][1]);
    
27. 
    
28.       boolean switched = false;
    
29.       if (record[0][1] > record[1][1]) {
    
30.         int[] temp = record[0];
    
31.         record[0] = record[1];
    
32.         record[1] = temp;
    
33.         switched = true;
    
34.       }
    
35. 
    
36.       //passive2 >= passive1
    
37.       total += record[1][0] + record[1][1];
    
38.       record[1][0] = 0; //clean active2
    
39.       int diff = record[0][0] - record[1][1];
    
40.       record[0][0] = Math.max(0, diff);  //clean active1
    
41.       record[1][1] = Math.max(0, -diff);  //clean passive2 with active1
    
42.       diff = record[0][1] - record[1][1];
    
43.       record[0][1] = Math.max(0, diff);   //clean passive1
    
44.       record[1][1] = Math.max(0, -diff);  //clean passive2 with passive1
    
45.       total -= record[1][1];  //reduce rest of passive2 which will roll into next round
    
46. 
    
47.       if (switched) {
    
48.         int[] temp = record[0];
    
49.         record[0] = record[1];
    
50.         record[1] = temp;
    
51.       }
    
52.       System.out.println("--"+total);
    
53.     }
    
54.     total += record[0][1] + record[1][1];
    
55.     System.out.println("--"+total);
    
56.   }

复制代码

output:
3,10
4,15
--17
--19 (final result)

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

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

HC会直接丢掉难度过高的dp这一轮 不知道有些面试官是怎么想的 这样自己gHire里记录也好看不了吧。。

谢谢楼主分享！！

感觉greedy不行，应该还是要用dp。
目前有一点想法：dp长和宽分别是R1和R2的总时长，dp[i][j] = t表示R1运行i小时+R2运行j小时的情况下最小需要t时间。如果i，j所在的项目都是ACTIVE的话只能横着或竖着走，否则一律斜着走，再用个minheap每次选t最小值的点计算，最后跑完读取dp[sum1][sum2]。

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