p*****9
发帖数: 20 | 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*******e
发帖数: 1377 | 2 几个教室进行的同一活动是什么意思啊，是说一个活动可选教室有k个 任意一个教室办
了本次活动就算本次活动举办成功了，还是如果选这个活动几个教室必须全用上阿。 |
p*****9
发帖数: 20 | 3 应该不是几个教室必须全用上，因为从输入文件反映不出来某个活动必须用几个教室。
我感觉应该是可以用一个也可以用多个。但这也是我觉得奇怪的地方，既然用一个教室
就可以举办活动，那干嘛还占多个？实在搞不懂这条件有啥用。。。
【在 h*******e 的大作中提到】
: 几个教室进行的同一活动是什么意思啊，是说一个活动可选教室有k个 任意一个教室办
: 了本次活动就算本次活动举办成功了，还是如果选这个活动几个教室必须全用上阿。
|
h*******e
发帖数: 1377 | 4 如果是全用上做一个 dp , 开个 dp[1024] 扫 actNum遍就扫出来了把 满足题意多组
解阿，要求什么阿？ 活动最多的情况？ 全部打出来所有可能不大现实吧。
噢看出来了，我上面的算法没有考虑时间段会很多～～
如果不是全用上。。。似乎情况更多了啊。。 |
s***5
发帖数: 2136 | 5 那个条件的意思显然是说，一个活动可以在任何教室举行，所以有时候就需要在不同教
室间调节某个活动。 |
p*****9
发帖数: 20 | 6 刚同学跟我update一下说活动时间只是从9点到18点，以小时为单位，比如某个活动是
从9点到10店或者从13点到16点。
题目似乎也没说让列出活动最多的情况，只是说打印出所有满足条件的活动来。感觉一
个活动同时占多个教室没什么意义啊。。。
【在 h*******e 的大作中提到】
: 如果是全用上做一个 dp , 开个 dp[1024] 扫 actNum遍就扫出来了把 满足题意多组
: 解阿，要求什么阿？ 活动最多的情况？ 全部打出来所有可能不大现实吧。
: 噢看出来了，我上面的算法没有考虑时间段会很多～～
: 如果不是全用上。。。似乎情况更多了啊。。
|
p*****9
发帖数: 20 | 7 你的意思是说如果有一个活动在1点到5点举办，那它可以在1点到2点之间在c1, 2点到5
点之间在c2？我也想过，但是想不出来啥情况下需要在不同教室间换来换去。。。
【在 s***5 的大作中提到】
: 那个条件的意思显然是说，一个活动可以在任何教室举行，所以有时候就需要在不同教
: 室间调节某个活动。
|
h*******e
发帖数: 1377 | 8 比如第二个活动一到２点只能用第一个教室的教室。。 第一个活动如果灵活就要换了。
但是必然是要求某种极值阿。。 你再去问问。否则 都不选的情况，各个活动都选一
个的情况，还有各种排列组合， 情况太多了啊。
到5
【在 p*****9 的大作中提到】
: 你的意思是说如果有一个活动在1点到5点举办，那它可以在1点到2点之间在c1, 2点到5
: 点之间在c2？我也想过，但是想不出来啥情况下需要在不同教室间换来换去。。。
|
l*********b
发帖数: 65 | |
p*****9
发帖数: 20 | 10 OK 我再去问问, 本来挺简单的一个贪心题目，加了那个活动可以占多个教室的条件后
，一下乱了。。。
了。
【在 h*******e 的大作中提到】
: 比如第二个活动一到２点只能用第一个教室的教室。。 第一个活动如果灵活就要换了。
: 但是必然是要求某种极值阿。。 你再去问问。否则 都不选的情况，各个活动都选一
: 个的情况，还有各种排列组合， 情况太多了啊。
:
: 到5
|
s****h
发帖数: 3979 | 11 既然可以换活动室，那么教室就无所谓了。
题目简化为所有活动抢15个坑。
分三步
1.安排尽可能多的活动，一个活动某时段只能占一个坑；
2.如果15个坑没填满，让已经安排的活动多占点坑，提高坑的利用率。
3.尽量避免换教室
第一步就是看砍掉那些活动，使得每个时间段都小于等于15
第二步和第三步貌似需要合起来考虑，更复杂。 |
p*****9
发帖数: 20 | 12 嗯……感觉好复杂啊，头大TT
【在 s****h 的大作中提到】
: 既然可以换活动室，那么教室就无所谓了。
: 题目简化为所有活动抢15个坑。
: 分三步
: 1.安排尽可能多的活动，一个活动某时段只能占一个坑；
: 2.如果15个坑没填满，让已经安排的活动多占点坑，提高坑的利用率。
: 3.尽量避免换教室
: 第一步就是看砍掉那些活动，使得每个时间段都小于等于15
: 第二步和第三步貌似需要合起来考虑，更复杂。
|
r***3
发帖数: 3 | 13 整个过程可以用DFS （不知道还有没有更好的解法）
对于一个活动占多个教室，可以把每一个活动分为三种情况，分别占有1，2，3个教室
。贪心的时候，选中其中一种情况，但是把3个都标记为visited，以免在后面被重复选
中。
【在 p*****9 的大作中提到】
: 嗯……感觉好复杂啊，头大TT
|
b******g
发帖数: 3616 | 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就放进去。但是发现这个解法用不到题里的这个
|
