直觉
我会尽力而为。一种天真的方法是枚举所有可能的解，并选择最佳的一个。因此，找到可以容纳n个会议的k个房间等价于在n个点中找到k路划分。一个5个会议的2路划分示例是[0,2,4]和[1,3]，如OP示例所示：
|---0------| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
所以基本思想是枚举所有n个会议的k路划分，其中约束条件是两个重叠的会议不能属于同一组。例如，[0,1,2]和[3,4]不是有效的划分，因为会议[0,1,2]不能在同一个房间举行；对于会议[3,4]也是如此。幸运的是，使用递归方法时，这个约束条件很容易实现。
算法如下(Python代码)：
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 :
yield [ A[:] ]
elif k == len(A) :
yield [ [a] for a in A ]
else :
for partition in kWay( A[1:], k, overlap ) :
for i, ci in enumerate( partition ) :
isCompatible = all( A[0] not in overlap[x] for x in ci )
res = partition[:i] + [ ci + [ A[0] ] ] + partition[ i+1: ]
if isCompatible :
yield res
for partition in kWay( A[1:], k-1, overlap ) :
isValid = ( set(A[1:]) & set.union( * ( overlap[a] for a in A[ 1: ] ) ) == set() )
if (k-1>1) or ( k-1==1 and isValid ) :
yield partition + [ [ A[0] ] ]
这看起来有点复杂，但当你意识到这只是递归算法的
k路分区+2行额外代码以确保我们只考虑有效分区时，它实际上非常简单。
OP示例的解决方案：
现在让我们使用OP示例来准备输入数据。
import collections
n = 5
k = 2
A = range(n)
pairs = [ (0,1), (1,2), (2,3), (3,4) ]
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}
现在我们只需遍历有效的
2路分区并打印房间大小。只有一个有效的分区，所以这就是我们的解决方案：
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]
好的，会议 1,3 需要一个大小为 10 的房间，而会议 0,2,4 则需要一个大小为 10 的房间。
稍微复杂一些的例子
但是只有一种有效的 2-路分区，所以这当然也是最优解。太无聊了！让我们添加一个新的会议 5 和一个新的房间到 OP 示例中，使其更加有趣：
|---0------| |---5---| |---------4---------|
|------1-----| |----------3-----------|
|--------2-------|
相应的输入数据：
n = 6
k = 3
A = range(n)
pairs = [ (0,1), (1,2), (2,3), (3,4), (5,2), (5,3) ]
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}
结果如下：
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]
最优的3路分区是[[3, 1], [4, 2, 0], [5]]，最优房间尺寸为[10, 10, 2]。您还可以直接获取所有房间的最小尺寸：
min( sum( [ max( size[x] for x in c ) for c in partition ] ) for partition in kWay( A, k, overlap ) )
22
