楼主: rasperrypie
跳转到指定楼层
上一主题 下一主题
收起左侧

Snapchat挂经

🔗
pawprinter 2016-10-2 05:09:14 | 只看该作者
全局:
rasperrypie 发表于 2016-10-2 04:12
嗯嗯,我理解你的意思了,是这个解法?
http://www.geeksforgeeks.org/build-lowest-number-by-removing ...

我说的是O(n)解法,一个deque可解
回复

使用道具 举报

🔗
ericlee27 2016-10-2 23:45:12 | 只看该作者
全局:
楼主那个meeting rooms with weights 怎么解得?
回复

使用道具 举报

🔗
pawprinter 2016-10-3 02:41:59 | 只看该作者
全局:
ericlee27 发表于 2016-10-2 23:45
楼主那个meeting rooms with weights 怎么解得?

按照结束时间排序,然后动态规划解
回复

使用道具 举报

🔗
ericlee27 2016-10-3 02:54:39 | 只看该作者
全局:
pawprinter 发表于 2016-10-3 02:41
按照结束时间排序,然后动态规划解

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

使用道具 举报

🔗
pawprinter 2016-10-3 03:09:54 | 只看该作者
全局:
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的时间复杂度呀?
多谢了
回复

使用道具 举报

🔗
pawprinter 2016-10-11 12:37:09 | 只看该作者
全局:
小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楼说的最优解是怎么得到的呢? 大良神赐教啊
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表