Optimal room count and sizes for N overlapping Meeting Schedules

Question

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 ?

Answer 1

Here is my solution by java.

class Meeting{

    LocalTime start;
    LocalTime end;
    Meeting(LocalTime start, LocalTime end){
        this.start = start;
        this.end = end;
    }
}


public static int meeingRoom(List<Meeting> list){


    //use queue structure to store the room in use
    Queue<Meeting> rooms = new LinkedList<Meeting>();
    rooms.add(list.get(0)); 

    for(int i = 1; i< list.size(); i++){ 

         Meeting current = list.get(i); 

         //max: keep the max of ever occupied
         //occupied: so far occupied room

         int  max = 1, occupied = 1; 
         List<Meeting> rooms = new ArrayList<Meeting>();
         rooms.add(list.get(0));

         for(int i = 1; i< list.size(); i++){ 

            Meeting current = list.get(i); 
            int roomSize = rooms.size();

            //check all previous rooms to release finish room
            for(int j = 0; j < roomSize; j++){ 
               if(j >= rooms.size()) break;

               Meeting previous = rooms.get(j);

               if(current.start.compareTo(previous.end) >= 0){ 
                   rooms.remove(j);
               } 

           rooms.add(current); 

           //when all the rooms once occupied, all remove
           //reset the occupied
           if(rooms.size() == 1 ){ 
               max = Math.max(occupied, max);
               occupied = 1; 
           }else{ 
              occupied = Math.max(occupied, rooms.size()); 
           };


    }

    //the last time added room hasn't been check
    return Math.max(occupied, max);
}

Answer 2

import java.util.*;
    class Codechef
     {
         //Sorting by exchange
         public static int[] Sort(int arr[],int n)
         {
             int temp=0;
             for(int i=0;i<n-1;++i)
             {
                 for(int j=i+1;j<n;++j)
                 {
                     if(arr[i]>arr[j])
                     {
                         temp=arr[i];
                         arr[i]=arr[j];
                         arr[j]=temp;
                     }
                 }
            }
            return arr;
        }
        public static void main (String[] args) throws java.lang.Exception
        {
            Scanner sc = new Scanner(System.in);
            int n=0; //n : Total number of trains arriving on the platform
            n=sc.nextInt();
            String UserInp;
            String [] inp = new String[n]; //inp[] : Accepting the user input ....Arrival time#Departure time
            int []Ar = new int[n];
            int []Dp = new int[n];
            for(int i=0;i<n;++i)
            {
                UserInp=sc.next();
                inp[i]=UserInp;
            }
            System.out.println("Displaying the input:\n");
            for(int i=0;i<n;++i)
            {
                System.out.println("inp[i] : "+inp[i]);
            }
            for(int i=0;i<n;++i)
            {
                String temp=inp[i];
                String a=temp.substring(0,2);
                String b=temp.substring(3,5);
                String c=temp.substring(6,8);
                String d=temp.substring(9);
                System.out.println("a : "+a);
                System.out.println("b : "+b);
                String x=a+b;
                Ar[i]=Integer.parseInt(x);
                System.out.println("x : "+x);
                System.out.println("c : "+c);
                System.out.println("d : "+d);
                String y=c+d;
                Dp[i]=Integer.parseInt(y);
                System.out.println("y : "+y);
            }
            System.out.println("Displaying the arrival time : ");
            for(int i=0;i<n;++i)
            {
                System.out.println(Ar[i]);
            }
            System.out.println("Displaying the departure time : ");
            for(int i=0;i<n;++i)
            {
                System.out.println(Dp[i]);
            }
            Ar=Sort(Ar,n);
            System.out.println("Displaying arrival time in ascending order :");
            for(int i=0;i<n;++i)
            {
                System.out.println(Ar[i]);
            }
            Dp=Sort(Dp,n);
            System.out.println("Displaying departure time in ascending order :");
            for(int i=0;i<n;++i)
            {
                System.out.println(Dp[i]);
            }
            int count=0;
            int need=0;
            int i=0,j=0;
            while(i<n && j<n)
            {
                if(Ar[i]<Dp[j])
                {
                    ++need;
                    if(need>count)
                    {
                        count=need;
                    }
                ++i;
            }
            else if(Ar[i]>Dp[j])
            {
                --need;
                ++j;
            }
            if(need==-1)
            {
                break;
            }
        }
        if(need!=-1)
        {
            System.out.println("Required answer : "+count);
        }
        else
        {
            System.out.println("Invalid input");
        }

    }
}

    Input:
    6
    09:00#09:10
    12:00#09:40
    09:50#11:20
    11:00#11:30
    15:00#19:00
    18:00#20:00

    Output:
    Displaying the input:

    inp[i] : 09:00#09:10
    inp[i] : 12:00#09:40
    inp[i] : 09:50#11:20
    inp[i] : 11:00#11:30
    inp[i] : 15:00#19:00
    inp[i] : 18:00#20:00
    a : 09
    b : 00
    x : 0900
    c : 09
    d : 10
    y : 0910
    a : 12
    b : 00
    x : 1200
    c : 09
    d : 40
    y : 0940
    a : 09
    b : 50
    x : 0950
    c : 11
    d : 20
    y : 1120
    a : 11
    b : 00
    x : 1100
    c : 11
    d : 30
    y : 1130
    a : 15
    b : 00
    x : 1500
    c : 19
    d : 00
    y : 1900
    a : 18
    b : 00
    x : 1800
    c : 20
    d : 00
    y : 2000
    Displaying the arrival time : 
    900
    1200
    950
    1100
    1500
    1800
    Displaying the departure time : 
    910
    940
    1120
    1130
    1900
    2000
    Displaying arrival time in ascending order :
    900
    950
    1100
    1200
    1500
    1800
    Displaying departure time in ascending order :
    910
    940
    1120
    1130
    1900
    2000
    Invalid input

    The above is a detailed solution for the approach stated in the link below:
    http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

Answer 3

I believe that this problem is equivalent to "Minimum Number of Platforms Required for a Railway/Bus Station" problem.

This article http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/ explains well how to approach it.

Answer 4

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

Answer 5

To find the minimum number and capacity of meeting rooms needed to conduct all meetings, you first need to schedule those meetings optionally to the rooms (with a score function that minimizes the number of capacity of rooms). That scheduling (similar to course scheduling) is NP-complete or NP-hard. That implies that your problem is too.

That, in turn, implies that there's no known algorithm for your problem that is optimal and scales out. Greedy algorithms (including your example) won't be consistently optimal (or not even near optimal if you have more constraints) - but at least they'll scale :) To get even better results (if needed), look into optimization algorithms, such as metaheuristics.

Answer 6

Consider this scenario:

(m1) |-3-|
(m2)  |--2--|
(m3)   |--1--|
(m4)      |-1-|
(m5)       |-2-|

Your solution will proceed as such:

1. {3} (First room created)
2. {3, 2} (Two meetings at same time, second room needed)
3. {3, 2, 1} (Three meetings at same time, third room needed)
4. {3, 2, 1} (m1 is over so m4 goes into the 3-room)
5. {3, 2, 1, 2} (Four meetings at same time, fourth room needed, create room at same size as newest meeting)

This solution has a cumulative capacity of 8.

Now consider this solution: {3, 2, 1, 1}. It has a cumulative capacity of 7.
At step (4) above, m4 will go into the unoccupied 1-room and the 3-room is still open. Thus, that is where m5 will go.

Assumptions Made

1. The optimal solution is first ranked on number of rooms: it will have the lowest number of rooms. The second criteria is that it will have the lowest cumulative capacity: the sum of the capacities of each room.
2. As your solution is identified as greedy when you have to create a room you will create one of the size of the room being evaluated.
3. Two meetings cannot be in the same room at one time, regardless of size.

Algorithm Alteration

Update: I just realized that even with this alteration creating a room can still lead to sub-optimal solutions. The reason is that one could resize existing rooms before creating a new room.

As an example, say we have four meetings in four rooms.

• m1 (size 4) is in a 4-room
• m2 (size 2) is in a 4-room
• m3 (size 1) is in a 2-room
• m4 (size 1) is in a 2-room

And we seek to add m5 (size 5). My proposed algorithm alteration would create a new 5-room, adding 5 to the cumulative capacity. However, we could resize m2's room to be a 5-room, have m5 go there, and create a new room for m2 of size 2. This would only add 2 to the cumulative capacity.

One may wonder why not put m2 into one of 2-rooms (displacing m3) and create a new 1-room. Resizing rooms is more difficult as we can't guarantee that room will be open when the meeting that needs it starts. Adding rooms is easier because then that room will always have been there; it wasn't being used since we just created it at this step in the algorithm.

Sub-optimal Algorithm Alteration As noted above, this is proven to be sub-optimal but I'm keeping it here until I can think of a better alternative.

To account for the scenario above you will need to do some extra work anytime you have to create a new room:

1. Find a list of all meetings currently active (including the one you're currently evaluating).
2. Start at the largest meeting and assign each meeting to a room.
3. When you reach a meeting that cannot be assigned that is the size of the room you must create.

Thus, in the example above, this alteration comes into play at step 5 when a new room needs to be created. Explanation per step above:

1. All meetings currently active: {m2, m3, m4, m5}. For the record, current rooms are {3, 2, 1}
2. Starting with largest, assign each meeting to a room {m2 goes to 3-room, m5 goes to 2-room, m3 goes to 1-room}
3. m4 is stuck without a room. Thus we must create a room for it. m4 is size 1 so the new room is also size 1.