一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 392|回复: 8
收起左侧

[算法题] 求助求助:interval schedule, n room for most number of meetings with priority

[复制链接] |试试Instant~ |关注本帖
jasusy 发表于 2015-8-2 10:27:05 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一道算法题,真是抓破脑皮:
給你m个meeting(meeting id, start时间,end 时间,priority) 和n个rooms,要求安排尽量多的的meetings, 但是高优先级要优先考虑,即使2个低priority换一个高priority也不行!输入是m,n和好多个string,一个string包含meeting id, start时间,end 时间,priority。 返回安排进去了n个room里面的meeting 的id(按顺序)

for example:
INPUT:
3(# of rooms)
5(# of meetings)
1, 1300, 1400, 100(priority) "meeting 1"
2, 1345, 1445, 100, " meeting 2"
3, 1330, 1350,100 ,“meeting 3”
4,1500, 1700, 75,”meeting 4“
5, 1300,1400,90,”meeting 5“

OUTPUT:
1 3 2 4 (会议的序列)。

现在我想到的方法是:
先根据priority sort,然后在每一个相同priority里再根据结束时间sort。 在从上到下往房间里排,一个房间不行换下一个,如果有compatible的时间,只能drop这个meeting,继续序列里下一个。

这个方法开始我觉得没有问题。但是后来想了很久又发现有问题
比如, 3 个room,meeting如下
priority 100:
----------
      ------------
      ------------
      ------------
priority 90:
----
----
----

这个例子,如果按照我之前说的greedy,会安排如2*90 + 3*100 5个meeting
----------
----  ------------
----  ------------
但是如如果把第一个100 priority的换成另一个,就能把剩下的90 priority 也安排景进去,相当于多了一个90 priority的meeting!!:
----  ------------
----  ------------
----  ------------

所以,高priority同样数量,不同排法肯能影响后面低priority的结果, 有没有办法排高priority是低priority有最大数量的可能
想不出来这个用什么方法解决。

大家都来凑个热闹讨论一下呗。也拜求大神路过指导!


larry_cn 发表于 2015-8-2 12:47:13 | 显示全部楼层
现在想到的 笨方法是
当高优先级 排列 可能出现 相同结果的 多种 set 组合时  把 每种情况都 列出来
再 依次 向 低优先级  用同样的 办法 罗列。。。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-2 13:56:00 | 显示全部楼层
好像另一个版块讨论过了吧?
我想了个很麻烦的线段树解法,其他人想出了比较简洁的排序+贪心的做法。
楼主可以搜一下帖子,就是同一个问题吧。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-2 14:02:31 | 显示全部楼层
zhuli19901106 发表于 2015-8-1 21:56
好像另一个版块讨论过了吧?
我想了个很麻烦的线段树解法,其他人想出了比较简洁的排序+贪心的做法。
楼 ...

恩,看过帖子。我想到的方法就跟你说的排序贪心算法一样的。当时有问题。就如我举得例子。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-2 14:03:04 | 显示全部楼层
larry_cn 发表于 2015-8-1 20:47
现在想到的 笨方法是
当高优先级 排列 可能出现 相同结果的 多种 set 组合时  把 每种情况都 列出来
再  ...

恩,感觉只会brute force了
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-2 14:17:00 | 显示全部楼层
首先, 我不明白什么是高优先级要优先考虑. 这个有歧义的.
应该是在xxxx的情况下, 高优先级要优先考虑
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-2 14:17:51 | 显示全部楼层
本帖最后由 readman 于 2015-8-2 14:27 编辑

- - 仔细看了一下, 发现原来是最简单的带权js问题. 搜下weighted job schxxxxxling problem把...

回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-2 14:28:54 | 显示全部楼层
readman 发表于 2015-8-1 22:17
首先, 我不明白什么是高优先级要优先考虑. 这个有歧义的.
应该是在xxxx的情况下, 高优先级要优先考虑

就是如果有空间给高优先级的放下,不管这个高优先级占用掉的空间够多少个低优先级放,都先放这个高优先级的。高优先级的没得放再考虑低优先级。
回复 支持 反对

使用道具 举报

 楼主| jasusy 发表于 2015-8-2 14:29:00 | 显示全部楼层
readman 发表于 2015-8-1 22:17
- - 仔细看了一下, 发现原来是最简单的带权js问题. 搜下weighted job schxxxxxling problem把...

不是吧, 100 priority有4个,但是我的意思是room只有三个, 所以100priority的不管怎么样都只能有三个,问题是greedy怎么能够得到跟多的90 priority。 恩,看来是我的表达不是很清楚。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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