Google 面经

倒序浏览 · 2021-9-10 12:50:11

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

面试一道题目没什么特别好的思路，想问问大家有什么想法/LC原题？

给了两个recipe R1 和 R2，每个recipe有特定的几个步骤，每个步骤是一个tuple

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

的办法，唯一的做法是计算所有可能，时间是 2**min(m, n)
有人有什么更好的思路吗？

nagato

楼上的解法对于
R1 = [(3, 'ACTIVE'), (10, 'PASSIVE')]
R2 = [(4, 'ACTIVE'), (15, 'PASSIVE')]
来说，全都是错的。。。最优是先处理R2的第一个，然后并行处理R1的所有任务，最优时间4+15==19

南宫狗剩

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

majiamajia1212

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

感觉应该是这个思路

q623139979

R1里的所有active相加的sa1，passive相加sp1；R2相同操作，sa2，sp2.
result=(sa1 - min( (sa1-sp2), 0)) + (sa2 - min( (sa2-sp1), 0))

ShawnDDD

q623139979 发表于 2021-09-09 22:06:31
R1里的所有active相加的sa1，passive相加sp1；R2相同操作，sa2，sp2.
result=(sa1 - min( (sa1-sp2), 0)) + (sa2 - min( (sa

忘记讲了，R1和R2里面的顺序不可以改变

匿名用户-OOWJY *2021-9-10 20:50:57* · 2021-9-10 20:50:57

感觉可以2 pointer, 遇到都是active，先执行小的，同时move pointer forward, 两个一个active 一个passive 或者都是passive，同时执行，并根据情况看移动指针

匿名用户-ZWF7Z *2021-9-11 23:47:43* · 2021-9-11 23:47:43

loop两个recipe list,把所有active的步骤所需的时间相加，然后加max(sum of all passive step in recipe 1,sum of all passive step in recipe 2)?

来自APP · 2021-9-12 15:52:43

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

大卫李

My gut tells me it is a DP problem. But I cannot figure it out yet.

匿名用户-FO7QA *2021-9-13 10:21:44* · 2021-9-13 10:21:44

匿名者发表于 2021-9-12 00:52
想问问如果一个passive的任务时间够长的话，可以去做另一个list里的多个paasive或active的任务吗例如r1里 ...

当然可以啦

ghu97

想到一个greedy的做法，不确定对不对，有没有test case可以试一试？
就是优先做Passive开头的任务，然后都开头都是active，则选择做剩余时间长的任务。直到全都做完。