I bumped into this question and I am not sure if my solution is optimal.
Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules) , find the minimum number "&" capacity of meeting rooms needed to conduct all meetings.
|---10------|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .|---------8---------|
|------8-----| |----------10-----------|
|--------6-------|
For the above schedule, we would need two meeting rooms of 10 and 10 capacitities. ( am i correct ? )
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..
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.
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.
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.
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