Google面试题请教 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Google面试题请教

Google面试题请教# JobHunting - 待字闺中

p*92014-09-25 07:09

1 楼

前两天我同学面了G家被问了一道题，事后跟我讨论了一下，但两人都不确定自己想出
的算法是否正确，所以发上来问问各位大神。
题目是这样的：学校的club需要申请活动教室来举办活动。学校一共有5个活动教室（
c1,c2,c3,c4,c5），每个教室在同一时段最多只能同时被3个活动占用，而且同一个活
动在同一时间段内可以同时在几个教室进行（比如活动a1可以在1点到两点之间可以同
时在c1和c2举办活动）。现在给你一份学校各种club的活动申请表，让你挑出符合上述
条件的所有活动来。input是个txt文件，里面有活动的Id,开始时间，终止时间。
Output只需打印出活动id，教室id，开始时间，结束时间。
我想出的解法是简单的贪心算法，就是按照活动的结束时间排序，然后对于每一个活动
遍历5个教室，如果overlap小于等于3就放进去。但是发现这个解法用不到题里的这个
条件：“而且同一个活动在同一时间段内可以同时在几个教室进行”。我跟同学讨论半
天也不知道咋利用这个条件，是不是我们理解得有问题？
求各位指点一二，多谢~~

h*e2014-09-25 07:09

2 楼

几个教室进行的同一活动是什么意思啊，是说一个活动可选教室有k个任意一个教室办
了本次活动就算本次活动举办成功了，还是如果选这个活动几个教室必须全用上阿。

p*92014-09-25 07:09

3 楼

应该不是几个教室必须全用上，因为从输入文件反映不出来某个活动必须用几个教室。
我感觉应该是可以用一个也可以用多个。但这也是我觉得奇怪的地方，既然用一个教室
就可以举办活动，那干嘛还占多个？实在搞不懂这条件有啥用。。。

【在 h*******e 的大作中提到】

: 几个教室进行的同一活动是什么意思啊，是说一个活动可选教室有k个任意一个教室办
: 了本次活动就算本次活动举办成功了，还是如果选这个活动几个教室必须全用上阿。

h*e2014-09-25 07:09

4 楼

如果是全用上做一个 dp , 开个 dp[1024] 扫 actNum遍就扫出来了把满足题意多组
解阿，要求什么阿？活动最多的情况？　　全部打出来所有可能不大现实吧。
噢看出来了，我上面的算法没有考虑时间段会很多～～
如果不是全用上。。。似乎情况更多了啊。。

s*52014-09-25 07:09

5 楼

那个条件的意思显然是说，一个活动可以在任何教室举行，所以有时候就需要在不同教
室间调节某个活动。

p*92014-09-25 07:09

6 楼

刚同学跟我update一下说活动时间只是从9点到18点，以小时为单位，比如某个活动是
从9点到10店或者从13点到16点。
题目似乎也没说让列出活动最多的情况，只是说打印出所有满足条件的活动来。感觉一
个活动同时占多个教室没什么意义啊。。。

【在 h*******e 的大作中提到】

: 如果是全用上做一个 dp , 开个 dp[1024] 扫 actNum遍就扫出来了把满足题意多组
: 解阿，要求什么阿？活动最多的情况？　　全部打出来所有可能不大现实吧。
: 噢看出来了，我上面的算法没有考虑时间段会很多～～
: 如果不是全用上。。。似乎情况更多了啊。。

p*92014-09-25 07:09

7 楼

你的意思是说如果有一个活动在1点到5点举办，那它可以在1点到2点之间在c1, 2点到5
点之间在c2？我也想过，但是想不出来啥情况下需要在不同教室间换来换去。。。

【在 s***5 的大作中提到】

: 那个条件的意思显然是说，一个活动可以在任何教室举行，所以有时候就需要在不同教
: 室间调节某个活动。

h*e2014-09-25 07:09

8 楼

比如第二个活动一到２点只能用第一个教室的教室。。　第一个活动如果灵活就要换了。
但是必然是要求某种极值阿。。　你再去问问。否则　都不选的情况，各个活动都选一
个的情况，还有各种排列组合，　情况太多了啊。

到5

【在 p*****9 的大作中提到】

: 你的意思是说如果有一个活动在1点到5点举办，那它可以在1点到2点之间在c1, 2点到5
: 点之间在c2？我也想过，但是想不出来啥情况下需要在不同教室间换来换去。。。

l*b2014-09-25 07:09

9 楼

天哪好难。。

p*92014-09-25 07:09

10 楼

OK 我再去问问, 本来挺简单的一个贪心题目，加了那个活动可以占多个教室的条件后
，一下乱了。。。

了。

【在 h*******e 的大作中提到】

: 比如第二个活动一到２点只能用第一个教室的教室。。　第一个活动如果灵活就要换了。
: 但是必然是要求某种极值阿。。　你再去问问。否则　都不选的情况，各个活动都选一
: 个的情况，还有各种排列组合，　情况太多了啊。
:
: 到5

s*h2014-09-25 07:09

11 楼

既然可以换活动室，那么教室就无所谓了。
题目简化为所有活动抢15个坑。
分三步
1.安排尽可能多的活动，一个活动某时段只能占一个坑；
2.如果15个坑没填满，让已经安排的活动多占点坑，提高坑的利用率。
3.尽量避免换教室
第一步就是看砍掉那些活动，使得每个时间段都小于等于15
第二步和第三步貌似需要合起来考虑，更复杂。

p*92014-09-25 07:09

12 楼

嗯……感觉好复杂啊，头大TT

【在 s****h 的大作中提到】

: 既然可以换活动室，那么教室就无所谓了。
: 题目简化为所有活动抢15个坑。
: 分三步
: 1.安排尽可能多的活动，一个活动某时段只能占一个坑；
: 2.如果15个坑没填满，让已经安排的活动多占点坑，提高坑的利用率。
: 3.尽量避免换教室
: 第一步就是看砍掉那些活动，使得每个时间段都小于等于15
: 第二步和第三步貌似需要合起来考虑，更复杂。

r*32014-09-25 07:09

13 楼

整个过程可以用DFS （不知道还有没有更好的解法）
对于一个活动占多个教室，可以把每一个活动分为三种情况，分别占有1，2，3个教室
。贪心的时候，选中其中一种情况，但是把3个都标记为visited，以免在后面被重复选
中。

【在 p*****9 的大作中提到】

: 嗯……感觉好复杂啊，头大TT

b*g2014-09-25 07:09

14 楼

咋感觉题目没讲明白？最终的目的是尽量安排最多的club还是什么？
另外为什么一个教室就能handle的活动需要放到几个教室里？教室有人数限制吗？
比如c1,c2教室，2-3点都有slot，现在有一个club a1在这个时间段活动，为什么不只
安排在c1,c2其中的一个教室而让其他club有机会用剩下的slot?这个条件是不是意味着
一个活动a1必须占用3个slot，但这3个slot可以在不同教室？

【在 p*****9 的大作中提到】

: 前两天我同学面了G家被问了一道题，事后跟我讨论了一下，但两人都不确定自己想出
: 的算法是否正确，所以发上来问问各位大神。
: 题目是这样的：学校的club需要申请活动教室来举办活动。学校一共有5个活动教室（
: c1,c2,c3,c4,c5），每个教室在同一时段最多只能同时被3个活动占用，而且同一个活
: 动在同一时间段内可以同时在几个教室进行（比如活动a1可以在1点到两点之间可以同
: 时在c1和c2举办活动）。现在给你一份学校各种club的活动申请表，让你挑出符合上述
: 条件的所有活动来。input是个txt文件，里面有活动的Id,开始时间，终止时间。
: Output只需打印出活动id，教室id，开始时间，结束时间。
: 我想出的解法是简单的贪心算法，就是按照活动的结束时间排序，然后对于每一个活动
: 遍历5个教室，如果overlap小于等于3就放进去。但是发现这个解法用不到题里的这个