N个重叠会议日程表的最佳房间数和大小

Question

我碰到了这个问题,我不确定我的解决方案是否是最佳的.

问题

给定N加权(Wi)和可能重叠的间隔(表示会议时间表),找到进行所有会议所需的会议室的最小数量"&".

例

|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|

        |------8-----|          |----------10-----------|

                  |--------6-------|

对于上述时间表,我们需要两个10和10个容量的会议室.( 我对么 ？ )

我的解决方案

如果我们有一个容量大于需要的会议室使用它,如果没有符合标准的会议室,建立新房间或增加现有房间,请从一个房间,并从左侧穿过间隔.新的能力.

例:

10点开始 - {10}

8点开始 - {10,8}

10月底结束 - {10-free,8}

6点开始 - {10,8}

结束8 - {10,8-free}

10的开头= {10,8 + = 2}或{10,10}

等等.....

这基本上是贪心的..

• 有人可以证明这不是最优的吗？
• 如果这是非最佳的解决方案是什么？DP？

Answer 1

我认为这个问题相当于"铁路/公交车站所需的最低平台数"问题.

这篇文章http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/很好地解释了如何处理它.

Answer 2

直觉

我会试试看。天真的方法是列举所有可能的解决方案并选择最佳解决方案。考虑到这一点，发现k室，可容纳n会议，就相当于找到k的三通分区n分。一的一个例子2的三通分区5会议是[ 0,2,4 ]和[ 1,3 ]在OP例如：

|---0------|                     |---------4---------|

   |------1-----|          |----------3-----------|

             |--------2-------|

因此，基本思想是枚举会议的所有k分区n，并具有两个重叠的会议不能属于同一群集的约束。例如，[ 0,1,2 ]并且[ 3,4 ]不是有效的分区，因为会议[ 0,1,2 ]不能在会议室中进行。会议也一样[ 3,4 ]。幸运的是，使用递归方法时，约束很容易实现。

算法

使用Python，它看起来像这样：

|---0------|                     |---------4---------|

   |------1-----|          |----------3-----------|

             |--------2-------|

这看起来有点复杂，但是当您意识到它只是用于k分区方式+ 2条额外行以保证我们仅考虑有效分区的递归算法时，它实际上非常简单。

OP示例的解决方案

好的，现在让我们使用OP示例准备输入数据：

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

现在，我们仅遍历有效的2路分区并打印房间大小。只有一个有效的分区，因此这是我们的解决方案：

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}

好吧，会议1,3要有一个大小的房间10，而会议0,2,4要有一个大小的房间10。

稍微复杂一点的例子

但是只有一个有效的2分区，因此这当然也是最佳解决方案。真无聊！让我们5在OP示例中添加一个新的会议和一个新的房间，使其更加有趣：

|---0------|            |---5---|        |---------4---------|

   |------1-----|          |----------3-----------|

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

结果：

|---0------|            |---5---|        |---------4---------|

   |------1-----|          |----------3-----------|

             |--------2-------|

最佳方式3分区为[[3, 1], [4, 2, 0], [5]]，最佳房间大小为[10, 10, 2]。您还可以直接获取所有房间的最小尺寸：

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}