Snapchat挂经

rasperrypie 发表于 2016-10-2 04:12
嗯嗯，我理解你的意思了，是这个解法？
http://www.geeksforgeeks.org/build-lowest-number-by-removing ...

我说的是O(n)解法，一个deque可解

楼主那个meeting rooms with weights 怎么解得？

ericlee27 发表于 2016-10-2 23:45
楼主那个meeting rooms with weights 怎么解得？

按照结束时间排序，然后动态规划解

pawprinter 发表于 2016-10-3 02:41
按照结束时间排序，然后动态规划解

我其实想请教的是转移方程式怎么想出来的，多谢

ericlee27 发表于 2016-10-3 02:54
我其实想请教的是转移方程式怎么想出来的，多谢

分两种情况，1. 当前meeting在最优解中，那么就找到meeting开始前结束最晚的时间点的总weights 加上当前的weight 2. 当前meeting不在最优解中，找到当前meeting结束前最晚的时间点的总weights

请问一下，follow up，如果每个meeting有权值，选一个没有conflict的meeting组合，使weight sum最大。
这个是什么意思说啊。 比如［1，3］［5，6］ ＋ ［2，4］ 和［1，3］ ＋［2，4］［5，6］的weightsum哪个大呢？
以及如何做到把所有可能的组合全部写出来呀。。。

pawprinter 发表于 2016-10-3 03:09
分两种情况，1. 当前meeting在最优解中，那么就找到meeting开始前结束最晚的时间点的总weights 加上当前 ...

请教一下， 这道题的意思是我只有一个room？
按照你的思路的话怎么做到NlogN的时间复杂度呀？
多谢了

小A要当码农 发表于 2016-10-11 11:23
请教一下， 这道题的意思是我只有一个room？
按照你的思路的话怎么做到NlogN的时间复杂度呀？
多谢了

卧槽。。zhuang神，这
就是N个meeting，按照结束时间排序，已经处理完的就扔进一个treeMap，key是结束时间。那么查找就是logN，所以总体NlogN吧 应该是这样

pawprinter 发表于 2016-10-11 12:37
卧槽。。zhuang神，这
就是N个meeting，按照结束时间排序，已经处理完的就扔进一个treeMap，key是结束时 ...

懂了， 所以说就是相当于一个room挑最大权重的meeting组合咯？
你onsite了吗

pawprinter 发表于 2016-10-11 12:37
卧槽。。zhuang神，这
就是N个meeting，按照结束时间排序，已经处理完的就扔进一个treeMap，key是结束时 ...

咦， 你这样做的话， 去TreeMap找的时候，如何找满足条件的（结束时间小于正在处理的meeting的开始时间）meeting中总累积权重最大的呢？

补充内容 (2016-10-11 13:11):
你的再35楼说的最优解是怎么得到的呢？ 大良神赐教啊