d******s
发帖数: 274 | 1 之前在板上看过这两个题的讨论，现在怎么也找不到了，不知道有没有大牛有这个链接
或者能给分析一下？
1. 给一天内一堆meeting的interval，求最少需要用几个meeting room ？
2. 所有员工需要参加一个meeting，给一段时间内所有员工的schedule， 然后每个员
工可以选择自己空闲时的两个slot 去参加 (只需要参加一次)。问怎么安排最少的
meeting ？
多谢！ |
t********2
发帖数: 28 | 2 Q1: sort the intervals by starting time， use a priority queue to store
available time for current rooms, then start from the first, check whether
there is a room available, if yes, use that one and reset its available time
, if not, add new room into the queue. At the same time, count the new rooms
which have been added into the queue. complexity ~ O(NlogN)
【在 d******s 的大作中提到】
: 之前在板上看过这两个题的讨论，现在怎么也找不到了，不知道有没有大牛有这个链接
: 或者能给分析一下？
: 1. 给一天内一堆meeting的interval，求最少需要用几个meeting room ？
: 2. 所有员工需要参加一个meeting，给一段时间内所有员工的schedule， 然后每个员
: 工可以选择自己空闲时的两个slot 去参加 (只需要参加一次)。问怎么安排最少的
: meeting ？
: 多谢！
|
d******s
发帖数: 274 | 3 谢谢 不知道这个能不能证明 之前看到的算法貌似是按结束时间从早到晚排序 不知道
有什么差别？
另外再问下第二题？趁周末自己顶一下…
time
rooms
【在 t********2 的大作中提到】
: Q1: sort the intervals by starting time， use a priority queue to store
: available time for current rooms, then start from the first, check whether
: there is a room available, if yes, use that one and reset its available time
: , if not, add new room into the queue. At the same time, count the new rooms
: which have been added into the queue. complexity ~ O(NlogN)
|
l*****a
发帖数: 14598 | 4 别人给出过很简单的算法
sort之后，使用一个counter
如果有meeting start, counter++
如果有meeting stop,counter--
最大counter就是需要的最多meeting room number
time
rooms
【在 t********2 的大作中提到】
: Q1: sort the intervals by starting time， use a priority queue to store
: available time for current rooms, then start from the first, check whether
: there is a room available, if yes, use that one and reset its available time
: , if not, add new room into the queue. At the same time, count the new rooms
: which have been added into the queue. complexity ~ O(NlogN)
|
p*****3
发帖数: 488 | 5 第一题是Graph coloring problem嘛，哎。。。 |
l*****a
发帖数: 14598 | 6 没听说过阿
三爷给讲讲？
【在 p*****3 的大作中提到】
: 第一题是Graph coloring problem嘛，哎。。。
|
d******s
发帖数: 274 | 7 谢谢！很有道理 所以如果要求具体方案的话就是按开始时间排序然后一个个insert
【在 l*****a 的大作中提到】
: 别人给出过很简单的算法
: sort之后，使用一个counter
: 如果有meeting start, counter++
: 如果有meeting stop,counter--
: 最大counter就是需要的最多meeting room number
:
: time
: rooms
|
p*****3
发帖数: 488 | 8
这个不对啊，可能需要的最少room比这个要多。
把一个interval看作一个graph node, overlapped的meeting算相连的点，一种颜色的
color看作一个meeting room. 相连点颜色不能相同，最少多少个颜色
【在 l*****a 的大作中提到】
: 别人给出过很简单的算法
: sort之后，使用一个counter
: 如果有meeting start, counter++
: 如果有meeting stop,counter--
: 最大counter就是需要的最多meeting room number
:
: time
: rooms
|
l*****a
发帖数: 14598 | 9
举个反例好吗？
这个值是某一时刻最多需要的room number ah
【在 p*****3 的大作中提到】
:
: 这个不对啊，可能需要的最少room比这个要多。
: 把一个interval看作一个graph node, overlapped的meeting算相连的点，一种颜色的
: color看作一个meeting room. 相连点颜色不能相同，最少多少个颜色
|
d******s
发帖数: 274 | 10 是找connected component的意思吗 建表O(n^2)遍历O(n) 最后返回最大组的成员个数
【在 p*****3 的大作中提到】
:
: 这个不对啊，可能需要的最少room比这个要多。
: 把一个interval看作一个graph node, overlapped的meeting算相连的点，一种颜色的
: color看作一个meeting room. 相连点颜色不能相同，最少多少个颜色
|
p*****3
发帖数: 488 | 11
不要，反正感觉不对就是了
【在 l*****a 的大作中提到】
:
: 举个反例好吗？
: 这个值是某一时刻最多需要的room number ah
|
p*****3
发帖数: 488 | 12
graph coloring, 找最小可用的颜色个数，DFS的那个吧
【在 d******s 的大作中提到】
: 是找connected component的意思吗 建表O(n^2)遍历O(n) 最后返回最大组的成员个数
|
