最佳房间数目和大小N重叠会议日程 [英] Optimal room count and sizes for N overlapping Meeting Schedules
问题描述
我碰到这个问题，我不知道如果我的解决方案是最佳的。
问题
指定N加权（无线），可能重叠的时间间隔（重新presenting会议日程），找到最小数和放大器;会议进行的所有会议室所需的能力。
示例
| --- 10 ------ |。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。| --------- --------- 8 |
| ------ 8 ----- | | ---------- ----------- 10 | | -------- ------- 6 |
有关上述安排，我们将需要10两间会议室和10 capacitities。 （对吗？）
我的解决方案
取一套房间，并遍历区间从左边，如果我们有一间会议室可提供容量大于所需使用它，如果没有符合标准，使一个新的房间或增加现有配备了新的能力。
例如：
开始的10 - {10}
的开始8 - {10，8}
10结束 - {10 - 免费的，8}
的开始6 - {10，8}
8结束 - {10，8，免费}
开始10 = {10，8 + = 2}或{10，10}
等等.....
这基本上是贪婪的。
- 有人能证明这一点非最佳？
- 请告诉我的解决方案，如果这是不是最佳？ DP？
直觉
我会试试看。天真的方法是枚举所有可能的解决方案，并挑选最好的一个。考虑到这一点，找到 K 室，可容纳 N 会议，就相当于找到一个氏/ code>往来港澳的 N 点分区。对 5 会议一个 2 往来港澳分区的一个例子是 [0,2,4 ] 和 [1,3] 在OP例如：
| --- 0 ------ | | --------- --------- 4 |
| ------ 1 ----- | | ---------- ----------- 3 |
| -------- ------- 2 |
所以，基本的想法是枚举所有 k的 -way分区，约束两个会议重叠不能属于同一个集群。例如， N 会议 [0,1,2] 和 [3,4] 并不是因为会议的有效分区 [0,1,2] 不能发生在室内;同样适用于会议 [3,4] 。幸运的是，约束是很容易使用递归的方法时实施。
算法
使用的Python ，它看起来是这样的：
高清粿（A，K，重叠）：
A =会议ID列表，房间的K =数，
重叠[会议ID M] =集会议与间重叠
如果k == 1：＃只有1室：所有会议去那里
屈服[A [：]
ELIF满足K == LEN（A）：＃N室和n会议：把每间客房1间会议
产生[A]为一间于A]
其他 ：
对于分区粿（A [1：]，K重叠）：＃添加新的会议，将一个现有房间
对于我，CI在历数（分区）：
相适应=所有（A [0]不重叠[X]对于x在CI）＃2避免重叠在同一个房间会议
RES =分区[我] + [CI + A [0]]] +分区[I + 1：]
如果相适应：
产量水库
对于分区粿（A [1：]，K-1，重叠）：＃添加新的会议，一个新的房间
的isValid =（一组（A [1：]）及set.union（*（重叠[A]为在A [1：]））==集（））＃2避免重叠在同一个房间会议
如果（k-1个→1）或（K-1 == 1和的isValid）：
产量分区+ [A [0]]]
这看起来有点复杂，但是当你意识到这只是递归算法 K 办法分区+ 2个额外的线路，以保证我们只考虑它其实很简单有效的分区。
OP例如解
好了，现在让我们prepare使用OP例如输入数据：
导入收藏
N = 5
K = 2
＃
A =范围（N）
字典＃prepare重叠
对= [（0,1），（1,2），（2,3），（3,4）]＃会议重叠
大小=字典（（（0,10），（1,8），（2,6），（3,10），（4,8）））
重叠= collections.defaultdict（套）
对（I，J）中对：
重叠[I]。新增（J）
重叠[J]。新增（I）
defaultdict（小于类型设定＆gt;中的{0：设置为（[1]），1：集（[0,2]），2：集（[1,3]），3：组（[2,1 4]），4：组（[3]）}）
{0：10，1：8,2：6,3：10,4：8}
现在我们只是遍历有效 2 往来港澳分区和打印房间的大小。世界上只有一个有效的分区，所以这是我们的解决方案：
在粿（A，K，重叠）分区：
打印分区，[最大（大小[X]对于x在三）对C的分区]
[[3,1]，[4,2，0]] [10，10]
确定这样的会议 1,3 去，房间面积 10 ，和会议 0,2,4 走在一个房间大小的 10 。
一个稍微复杂的例子
但是，只有一个有效的 2 -way分区，当然，这也是最佳的解决方案。如何无聊！让我们添加一个新的会议 5 和一个新房间的任择议定书的例子，使之更加有趣：
| --- 0 ------ | | --- 5 --- | | --------- --------- 4 |
| ------ 1 ----- | | ---------- ----------- 3 |
| -------- ------- 2 |
输入相应的数据：
N = 6
k = 3的
＃
A =范围（N）
对= [（0,1），（1,2），（2,3），（3,4），（5,2），（5,3）]＃会议重叠
大小=字典（（（0,10），（1,8），（2,6），（3,10），（4,8），（5,2）））
重叠= collections.defaultdict（套）
对（I，J）中对：
重叠[I]。新增（J）
重叠[J]。新增（I）
defaultdict（小于类型设定＆gt;中的{0：组（[1]），1：集（[0,2]），2：集（[1，3，5]），3：组（[ 2，4，5]），4：组（[3]），5：组（[2,3]）}）
{0：10，1：8,2：6,3：10,4：8,5：2}
和结果：
在粿（A，K，重叠）分区：
打印分区，[最大（大小[X]对于x在三）对C的分区]
[[3,1]，[4,2，0]，[5] [10，10，2]
[[3,1]，[4,2]，[5,0] [10，8，10]
[[3,0]，[4,2]，[5,1] [10，8,8]
[3]，[4,2，0]，[5，1]] [10，10,8]
[[4,5，1]，[3,0]，[2] [8，10，6]
[[4,5，1]，[3]，[2，0]] [8，10，10]
[[4,5，0]，[3,1]，[2] [10，10，6]
[[4,5]，[3,1]，[2，0]] [8，10，10]
最佳 3 往来港澳分区 [3,1]，[4,2，0]，[5]] 和最佳的房间大小 [10，10，2] 。您也可以在所有客房的最小大小直接：
分（SUM（[MAX（大小[X]对于x在C）对于C在分区]）的分区粿（A，K，重叠））
22
I bumped into this question and I am not sure if my solution is optimal.
Problem
Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules) , find the minimum number "&" capacity of meeting rooms needed to conduct all meetings.
Example
|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
|------8-----| |----------10-----------| |--------6-------|
For the above schedule, we would need two meeting rooms of 10 and 10 capacitities. ( am i correct ? )
My Solution
Take a set of rooms, and traverse the intervals from the left, if we have a meeting room available with a capacity greater than needed use it, if there is none that meets the criteria, make a new room or increment the existing rooms with the new capacity.
Example:
Start of 10 - { 10 }
Start of 8 - { 10, 8 }
End of 10 - { 10-free, 8 }
Start of 6 - { 10, 8 }
End of 8 - {10, 8-free }
Start of 10 = { 10, 8+=2 } OR {10, 10 }
and so on.....
this is essentially greedy..
- Can someone prove this non-optimal?
- Whats the solution if this is non-optimal? DP ?
Intuition
I will give it a try. The naive approach is to enumerate all possible solutions and pick the best one. With this in mind, finding k rooms which can accommodate n meetings is equivalent to finding a k-way partition of n points. An example of a 2-way partition of 5 meetings is [ 0,2,4 ] and [ 1,3 ] in the OP example:
|---0------| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
So the basic idea is to enumerate all k-way partitions of n meetings, with the constraint that two overlapping meetings cannot belong to the same cluster. For example, [ 0,1,2 ] and [ 3,4 ] is not a valid partition because meetings [ 0,1,2 ] cannot take place in the room; same goes for meetings [ 3,4 ]. Fortunately, the constraint is easy to implement when using a recursive approach.
Algorithm
With Python, it looks like this:
def kWay( A, k, overlap ) :
"""
A = list of meeting IDs, k = number of rooms,
overlap[ meeting ID m ] = set of meetings overlapping with m
"""
if k == 1 : # only 1 room: all meetings go there
yield [ A[:] ]
elif k == len(A) : # n rooms and n meetings: put 1 meeting per room
yield [ [a] for a in A ]
else :
for partition in kWay( A[1:], k, overlap ) : # add new meeting to one existing room
for i, ci in enumerate( partition ) :
isCompatible = all( A[0] not in overlap[x] for x in ci ) # avoid 2 overlapping meetings in the same room
res = partition[:i] + [ ci + [ A[0] ] ] + partition[ i+1: ]
if isCompatible :
yield res
for partition in kWay( A[1:], k-1, overlap ) : # add new meeting to a new room
isValid = ( set(A[1:]) & set.union( * ( overlap[a] for a in A[ 1: ] ) ) == set() ) # avoid 2 overlapping meetings in the same room
if (k-1>1) or ( k-1==1 and isValid ) :
yield partition + [ [ A[0] ] ]
This looks a bit complicated but it's actually quite simple when you realize that it is simply the recursive algorithm for kway partitioning + 2 extra lines to guarantee that we only consider valid partitions.
Solution of OP example
Ok now let's prepare the input data using the OP example:
import collections
n = 5
k = 2
#
A = range(n)
# prepare overlap dictionary
pairs = [ (0,1), (1,2), (2,3), (3,4) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3]), 3: set([2, 4]), 4: set([3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8}
Now we just iterate over the valid 2-way partitions and print the room sizes. There is only one valid partition, so this our solution:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0]] [10, 10]
Ok so meetings 1,3 go a room of size 10, and meetings 0,2,4 go in a room of size 10.
A slightly more complicated example
But there was only one valid 2-way partition, so of course this was also the optimal solution. How boring! Let's add a new meeting 5 and a new room to the OP example to make it more interesting :
|---0------| |---5---| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
Corresponding input data:
n = 6
k = 3
#
A = range(n)
pairs = [ (0,1), (1,2), (2,3), (3,4), (5,2), (5,3) ] # overlapping meetings
size = dict( ( (0,10), (1,8), (2,6) , (3,10), (4,8), (5,2) ) )
overlap = collections.defaultdict(set)
for (i,j) in pairs :
overlap[i].add(j)
overlap[j].add(i)
defaultdict(<type 'set'>, {0: set([1]), 1: set([0, 2]), 2: set([1, 3, 5]), 3: set([2, 4, 5]), 4: set([3]), 5: set([2, 3])})
{0: 10, 1: 8, 2: 6, 3: 10, 4: 8, 5: 2}
And the result:
for partition in kWay( A, k, overlap ) :
print partition, [ max( size[x] for x in c ) for c in partition ]
[[3, 1], [4, 2, 0], [5]] [10, 10, 2]
[[3, 1], [4, 2], [5, 0]] [10, 8, 10]
[[3, 0], [4, 2], [5, 1]] [10, 8, 8]
[[3], [4, 2, 0], [5, 1]] [10, 10, 8]
[[4, 5, 1], [3, 0], [2]] [8, 10, 6]
[[4, 5, 1], [3], [2, 0]] [8, 10, 10]
[[4, 5, 0], [3, 1], [2]] [10, 10, 6]
[[4, 5], [3, 1], [2, 0]] [8, 10, 10]
The optimal 3-way partition is [[3, 1], [4, 2, 0], [5]] and the optimal room sizes are [10, 10, 2]. You can also get the minimum size of all rooms directly:
min( sum( [ max( size[x] for x in c ) for c in partition ] ) for partition in kWay( A, k, overlap ) )
22
这篇关于最佳房间数目和大小N重叠会议日程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
