请教一到面试中遇到的meeting room变种

DevidXu 发表于 2019-8-29 03:44
楼主排序用的是开始时间，priority queue用的是结束时间，感觉没什么问题。但结果可以不唯一：比如输入是 ...

+1 我也觉得lz的思路没为什么问题

扫描线？？？

ziwei1992 发表于 2019-8-28 06:31
谢谢你的回复，能不能举个具体例子呢？还是不太懂。。。

我重新思考了一下这个问题，首先，楼主的结论是对的
但是，楼主可能没有办法证明自己的结论是正确的，所以面试官觉得你不对
因为面试官估计和我的想法是一样的

比如 当前状态
当前房间状体 room[i]表示 第i个的最后结束时间
room=[2,7]
接下来的安排s=[(8,100),(9,10)]
按楼主的算法就是
接下来会变成
room[7,100]
s=[(9,10)]

而如果用第二个房间
则状态变成了
room[2,100]
s=[(9,10)]

和前面相比 这是一种更优的状态

然而因为启动时间是按时间排序的
所以这种更优的状态并不会得到更优的结果
（如何得到这个结论是关键，只有解释清楚这个才能证明楼主的思路是对的，我估计就是面试官没想明白这一点）
所以才能用这种贪心做法来实现

哥大懒猫 发表于 2019-8-29 00:34
Greey is a perfect solution.
First come first serve. If meeting rooms are limited, apply more.
这 ...

哈哈，好办法！谢谢你帮我测试了下。。。我真的是，跪的不明不白。。。

DevidXu 发表于 2019-8-29 03:44
楼主排序用的是开始时间，priority queue用的是结束时间，感觉没什么问题。但结果可以不唯一：比如输入是 ...

当时我也忘了问，她就写了一个output我以为顺序无所谓

onewaymyway 发表于 2019-8-29 11:35
我重新思考了一下这个问题，首先，楼主的结论是对的
但是，楼主可能没有办法证明自己的结论是正确的，所 ...

谢谢你的回复。你这么一分析我觉得我可能是没明白面试官当时的意图。我以为就是输出最少的房间就行了，但也许她的意思是不仅要房间最少，还要所有房间尽可能早结束？比如你的例子如果没有（9， 10）的话，那么放完(8, 100)以后贪心比dp晚了5个时间单位结束。当时应该clarify问一下。。。

onewaymyway 发表于 2019-8-29 11:35
我重新思考了一下这个问题，首先，楼主的结论是对的
但是，楼主可能没有办法证明自己的结论是正确的，所 ...

有点不太理解，为什么 room[2, 100]会比room[7,100]更优呢？虽然说这边会觉得说2比7，但是我们已经把时间排序过了，所以在安排完8,100之后的所有的开始时间都会大于等于8，也就是说2|7对于后续的意义是一样的。