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

今天面了一个公司，来了一道meeting room变种。input是interval,比如 [(1, 3), (3, 5), (2, 4)]， 然后输出怎么安排schedule,比如上面这个例子就输出 [ [(1, 3), (3, 5)], [(2, 4)] ], 是一个list of list. 第一个sublist是第一个meeting room,第二个sublist是第二个room这种。我是用priority queue做，pq里存最每个room结束的时间。先list按开始时间sort一遍，然后对每一个interval, pq里pop出来最早结束的room,和当前的开始时间比较一下，有重合的话就新开一个room,没有重合就更新pop出来的这个room的结束时间。然后面试官说我这个方法是greedy, 有一些情况没考虑到，不work。。。但是我想不出来不对的test case, 请教下大家有什么不正确的test case呢？

代码如下：
def schedule(times):
    ans = []

    times.sort(key = lambda x: x[0])
    pq = []  # 存结束时间，和对应的room的index: (e, idx)
    heapify(pq)
    for i in range(len(times)):
        s, e = times[i]
        if not pq:
            ans.append([(s, e)])
            heappush(pq, (e, 0))
        else:
            last_t, idx = heappop(pq)  # pop出最早结束的时间和对应房间的index
            if last_t <= s:
                ans[idx].append((s, e))
                heappush(pq, (e, idx))
            else:
                heappush(pq, (last_t, idx)) #如果需要新开一个房间，当前最小的还是放回去pq里
                ans.append([(s, e)])
                heappush(pq, (e, len(ans) - 1))

    return ans

Greey is a perfect solution.
First come first serve. If meeting rooms are limited, apply more.
这道题的答案和meeting room II的答案应该是一样的，只是return的形式不同，楼主可以把你这个的算法return的结果改成room的数值，放进leetcode里面测试https://leetcode.com/problems/meeting-rooms-ii, 测试是通过的。个人以为面试官是搞混了背包问题。

from heapq import  *

class Solution:
    def minMeetingRooms(self, times: List[List[int]]) -> int:
        ans = []
        times.sort(key = lambda x: x[0])
        pq = []  # 存结束时间，和对应的room的index: (e, idx)
        heapify(pq)
        for i in range(len(times)):
            s, e = times[i]
            if not pq:
                ans.append([(s, e)])
                heappush(pq, (e, 0))
            else:
                last_t, idx = heappop(pq)  # pop出最早结束的时间和对应房间的index
                if last_t <= s:
                    ans[idx].append((s, e))
                    heappush(pq, (e, idx))
                else:                       # 如果需要新开一个房间，当前最小的还是放回去pq里
                    heappush(pq, (last_t, idx))
                    ans.append([(s, e)])
                    heappush(pq, (e, len(ans) - 1))
        return len(ans)

https://leetcode.com/problems/meeting-rooms-ii

from heapq import  *

class Solution:
    def minMeetingRooms(self, times: List[List[int]]) -> int:
        ans = []
        times.sort(key = lambda x: x[0])
        pq = []  # 存结束时间，和对应的room的index: (e, idx)
        heapify(pq)
        for i in range(len(times)):
            s, e = times[i]
            if not pq:
                ans.append([(s, e)])
                heappush(pq, (e, 0))
            else:
                last_t, idx = heappop(pq)  # pop出最早结束的时间和对应房间的index
                if last_t <= s:
                    ans[idx].append((s, e))
                    heappush(pq, (e, idx))
                else:                       # 如果需要新开一个房间，当前最小的还是放回去pq里
                    heappush(pq, (last_t, idx))
                    ans.append([(s, e)])
                    heappush(pq, (e, len(ans) - 1))
        return len(ans)

测试通过

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)]

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

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

理论上讲你只管开始时间无法解决结束时间对后续选择的影响，所以这做不到当前选一个对于全局就是最优的
这题思路上还是得用动态规划 而且得根据结束时间来
因为只有根据结束时间才能确定前面所有的状态不会影响后面的选择

onewaymyway 发表于 2019-8-27 23:52
理论上讲你只管开始时间无法解决结束时间对后续选择的影响，所以这做不到当前选一个对于全局就是最优的
这 ...

谢谢你的回复，能不能举个具体例子呢？还是不太懂。。。

你能不能给一个朴素的解法, 一定能做出来的对的答案呢?

[1,10], [2,5], [3,6],[4,7]

337845818 发表于 2019-8-28 11:57
你能不能给一个朴素的解法, 一定能做出来的对的答案呢?

[1,10], [2,5], [3,6],[4,7]

暴力的话就是n^2, 两两互相比较？你的这个test case我刚用我的code跑了下，感觉没有问题，这是输出：[[(1, 10)], [(2, 5)], [(3, 6)], [(4, 7)]]， 需要四个房间。

我跟楼主思路一样哎 没明白哪里有问题？ 关注一下

马克一下。

onewaymyway 发表于 2019-8-27 23:52
理论上讲你只管开始时间无法解决结束时间对后续选择的影响，所以这做不到当前选一个对于全局就是最优的
这 ...

楼主排序用的是开始时间，priority queue用的是结束时间，感觉没什么问题。但结果可以不唯一：比如输入是[1,3], [2, 4], [5, 6]  那么就有两个答案，不知道面试官是否要求输出所有可能的解。