Optimal room count and sizes for N overlapping Meeting Schedules

algorithm, dynamic-programming, greedy, intervals, scheduling

Solution

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 `k`way 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

Problem

Original source