一亩三分地论坛

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

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

HackerRank 上的conference schedule 问题

[复制链接] |试试Instant~ |关注本帖
毛毛找工作 发表于 2015-7-28 01:55:45 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Rovi - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
given a series of meetings, each with a start time, end time and priority, schedule these meetings into a limited number of rooms, dropping the meetings that are lowest priority. from: 1point3acres.com/bbs
for example:
INPUT:. Waral 鍗氬鏈夋洿澶氭枃绔,
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:. 鍥磋鎴戜滑@1point 3 acres
1 3 2 4 (会议的序列)


请教下大牛们,有什么good idea?

评分

1

查看全部评分

zhuli19901106 发表于 2015-7-28 03:24:57 | 显示全部楼层
如果优先级高的会议一定要安排上的话,那就先按优先级排好序。
对于一个时间段为[100-130]的会议,可以理解为在时间轴上把这一区间加上1,表示这个时间段多了一个会议。
那么如果共有K个会议室,我们可以认为时间轴上任何点的值都不能大于K,因为同时进行的会议最多有K个。

于是我们关注整段+1区间求最大值这两个特点了。处理这些会议的思路如下:
1. 一开始,时间轴上所有点都是0
2. 按照优先级顺序,逐个把会议插入时间轴. 鍥磋鎴戜滑@1point 3 acres
3. 如果插入时,某段的最大值已经是K了,则表示会议室满了,排不开. 1point3acres.com/bbs
4. 否则,就可以插进去,整段区间+1
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
所以,能想到的思路可以是树状数组+RMQ,或者线段树。. visit 1point3acres.com for more.
而且要离散化处理,因为给的会议时间可以很大或很小,要收拢才能编程。

这么一看,感觉代码好复杂(x_x)
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-28 03:27:33 | 显示全部楼层
抱歉,树状数组+RMQ那个貌似不行。线段树应该可行。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-28 03:33:00 | 显示全部楼层
要输出序列的话,还需要按开始、结束时间,把那些能排上的会议进行排序。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-28 03:34:11 | 显示全部楼层
谁有简单些的方法吗,求分享~~
回复 支持 反对

使用道具 举报

Atomic123 发表于 2015-7-30 22:52:34 | 显示全部楼层
greedy algorithm

先sort所有meeting,按priority排序,priority相同按start time 排序,然后按sort的顺序greedy插入room
1.如果有room是empty的,插入当前meeting
2.如果所有room都满了,找到那个finishtime最早的room和他的finish time比较,如果finish time小于当前的meeting的start time,则替换,不然只能drop。
sorting 的时间复杂度是nlogn,找最小的finishtime可以是线性的,也可以维护一个heap,logm(n是meeting的数目,m是会议室的数目)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

topjoker 发表于 2015-7-31 12:24:19 | 显示全部楼层
link? 在哪里. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-31 15:09:54 | 显示全部楼层
感谢分享。想确认一下,是否“如果优先级为P的某会议没有得到安排,那么是否所有优先级<P的会议都不应该被安排”?比如
#Room = 1
#Conference = 3. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Conf1: 1300~1400, P = 100 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Conf2: 1330~1430, P = 90
Conf3: 1400~1500, P = 80
这种情况,答案应该是1还是1 3呢?按题目的字面意思,我的理解是只能安排1,因为1 3的话就不是“drop ... of the lowest priority”了。请问是不是这样?

补充内容 (2015-7-31 16:50):
又重看了下LZ给出的例子,并没有drop了最低优先级的会议,而是drop了一个中等优先级的会议。那么我想规则可能是“保证安排的会议数最多/房间利用率最高的情况下,尽可能drop优先级低的会议”?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-31 15:16:44 | 显示全部楼层
这题论坛里出现许多次了。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-7-31 15:18:48 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| 毛毛找工作 发表于 2015-8-1 08:24:30 | 显示全部楼层

市公司给的面试题
没有public link
回复 支持 反对

使用道具 举报

 楼主| 毛毛找工作 发表于 2015-8-1 08:27:12 | 显示全部楼层
stellari 发表于 2015-7-31 15:09
感谢分享。想确认一下,是否“如果优先级为P的某会议没有得到安排,那么是否所有优先级

先看的是优先级,在同样时间的开始时间,那么优先级高的会议开始了并且房间都满的情况下,drop掉所有低优先级的meeting。我想应该是这个会议~. visit 1point3acres.com for more.

. Waral 鍗氬鏈夋洿澶氭枃绔,补充内容 (2015-8-1 08:28):. 1point3acres.com/bbs
最后一句错了,我想应该是这个意思。
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 02:44:43 | 显示全部楼层
Atomic123 发表于 2015-7-30 06:52
greedy algorithm
-google 1point3acres
先sort所有meeting,按priority排序,priority相同按start time 排序,然后按sort的顺 ...

觉得有点问题啊,
比如:2 个room
id, start, end, priority
1,  0, 4,  100.1point3acres缃
2,  2, 5,  80
3,  3, 7,  80
4,  6, 10,  80
应该得到, 1, 2, 4 吧,如果用greedy, 会得到1, 3. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 03:08:42 | 显示全部楼层
Linzertorte 发表于 2015-7-30 23:18
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=116931

我看过你给的这个链接了,不过好像有点不一样:.1point3acres缃

那个只要输出bool,能不能全部安排进去,根据meeting开始和结束对应加减就行,超出就是false,
但是这题是安排尽量长时间高priority的结果。
相当于,给定n个room, 尽量多安排meeting,加了一个priority, 觉得要用dp但是还列不出推倒式。

大神能帮忙分析一下,或者给个链接什么的 吗?
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 03:17:13 | 显示全部楼层
想问一下,output是最多meeting,还是meeting时间加起来最长?
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 03:59:05 | 显示全部楼层
Atomic123 发表于 2015-7-30 06:52
greedy algorithm.1point3acres缃

先sort所有meeting,按priority排序,priority相同按start time 排序,然后按sort的顺 ...

你好,
看懂了一点,要求的是最多meeting数量,我理解成最长meeting时间了。.1point3acres缃
-google 1point3acres
但是有一个问题:
比如, 3 个room,meeting如下
priority 100:
----------
      ------------
      ------------
      ------------
priority 90:
----
----
----

这个例子,如果按照你所的greedy,会安排如2*90 + 3*100 5个meeting
----------
----  ------------
----  -------------google 1point3acres
但是如如果把第一个100 priority的换成另一个,就能把剩下的90 priority 也安排景进去,相当于多了一个90 priority的meeting!!:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
----  ------------
----  ------------
----  ------------
想不出来这个用什么方法解决。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-2 09:55:45 | 显示全部楼层
jasusy 发表于 2015-8-2 03:17
想问一下,output是最多meeting,还是meeting时间加起来最长?

这也是我一开始就想问的问题。这个条件如果没说清楚的话,这题就没法做了。我想应该是“meeting数目最多”,否则楼主给的例子中不应该安排只有20分钟的会议3,而是应该安排1小时的会议5。-google 1point3acres

另外还有个问题。假如我现在有5个会议,1个房间。有两种最佳方案,都只能排3个会议。方案1要扔掉的会议优先级是:100,30;方案2要扔掉的会议优先级是60, 40。那么我应该取哪种方案?

我想这个题是不是可以说成这样:

找出能使安排会议数目最大的方案。如果有多种方案都能实现这个最大数目,则在这些方案中选择“被抛弃的会议的平均priority最小”的那个方案。
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 10:04:00 | 显示全部楼层
stellari 发表于 2015-8-1 17:55
这也是我一开始就想问的问题。这个条件如果没说清楚的话,这题就没法做了。我想应该是“meeting数目最多 ...

我想应该是priority高的先保证,如果有空间给高priority的话。及时两个低priority跟他换也不行。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-2 10:42:30 | 显示全部楼层
jasusy 发表于 2015-8-2 10:04-google 1point3acres
我想应该是priority高的先保证,如果有空间给高priority的话。及时两个低priority跟他换也不行。

嗯,这种理解更合理一些。如果是这样的话我想可以表述成"select the schedule that minimizes the "maximum" priority of the dropped meetings". 比如我说的那个例子:方案1 drop 100,30,方案2 drop 60,40。那么应该选择方案2,因为方案2中被drop的最大priority只有60,而方案1被drop的最大priority为100。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

jasusy 发表于 2015-8-2 10:46:02 | 显示全部楼层
stellari 发表于 2015-8-1 18:42
嗯,这种理解更合理一些。如果是这样的话我想可以表述成"select the schedule that minimizes the "maxim ...

恩, 但是不知道怎么做,就像我之前提到的问题。。。

另外, 恭喜你成为勤奋农民,哈哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 16:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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