The optimal number of rooms and sizes for N overlapping meeting schedules

Question

I came across this question and I'm not sure if my solution is optimal.

Problem

Given N weighted (Wi) and possibly overlapping intervals (representing meeting schedules), find the minimum "&" bandwidth of conference rooms needed to hold all meetings.

Example

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

For the above schedule, we will need two conference rooms with 10 and 10 capacities. (I'm right?)

My decision

Take a set of rooms and go through the intervals on the left, if we have a meeting room with more capacity than necessary, use it, if there is not one that meets the criteria, make a new room or enlarge the existing rooms with a new capacity.

Example:

Start 10 - {10}

Start 8 - {10, 8}

End 10 - {10-free, 8}

Start 6 - {10, 8}

End 8 - {10, 8-free}

Start 10 = {10, 8 + = 2} OR {10, 10}

etc.

it's essentially greedy.

• Can anyone prove this to be suboptimal?
• What is the solution if this is not optimal? Dp?

Answer 1

Intuition

I'll try. The naive approach is to list all possible solutions and choose the best. With this in mind, looking for rooms k that can accommodate meetings n is equivalent to looking for a section k -way n . Section example 2 -way << 25>: [ 0,2,4 ] and [ 1,3 ] in the OP example:

 |---0------| |---------4---------| |------1-----| |----------3-----------| |--------2-------| 

Thus, the main idea is to list all k level sections of meetings n with the restriction that two overlapping meetings cannot belong to the same cluster. For example, [ 0,1,2 ] and [ 3,4 ] not a valid section because meetings [ 0,1,2 ] cannot be performed in a room; the same goes for meetings [ 3,4 ] . Fortunately, the restriction is easy to implement 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] ] ] 

It looks a bit more complicated, but it's actually quite simple when you realize that this is just a recursive algorithm for k ways of partitioning + 2 extra lines to ensure that we only consider valid sections.

Solution Example OP

Now let's prepare the input 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 sections and print the dimensions of the room. There is only one valid section, so this is 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] 

So, meetings 1,3 go to a room of size 10 , and meetings 0,2,4 go to a room of size 10 .

A slightly more complex example

But there was only one valid 2 -way section, so of course it was also the optimal solution. How boring! Add a new meeting 5 and a new room for the OP example, to make it more interesting:

 |---0------| |---5---| |---------4---------| |------1-----| |----------3-----------| |--------2-------| 

Relevant 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 section 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 2

I believe that this problem is equivalent to the task "Minimum number of platforms needed to work in a railway / bus station."

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

Answer 3

Consider this scenario:

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

Your decision will be as follows:

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

This solution has a total capacity of 8.

Now consider this solution: {3, 2, 1, 1}. It has an aggregate capacity of 7.
In step (4) above, m4 will enter an unoccupied 1-room room and the 3-room room is still open. So it will be m5.

Assumptions made

• The optimal solution is first evaluated by the number of rooms: it will have the lowest number of rooms. The second criterion is that it will have the smallest aggregate capacity: the sum of the possibilities of each room.
• Since your decision is identified as greedy, when you have to create a room you will create one of the sizes of the room that is evaluated.
• Two meetings cannot be in the same room at a time, regardless of size.

Change algorithm

Update : I just realized that even with this change, creating a room can still lead to suboptimal solutions. The reason is that you can resize existing rooms before creating a new room.

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

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

And we are trying to add m5 (size 5). My proposed change to the algorithm will create a new 5-room, adding 5 to the total capacity. However, we could change the size of the room m2 to be 5-room, have m5, and create a new room for m2 of size 2. This will add only 2 to the total capacity.

One may wonder why not put m2 in one of the two rooms (displacing m3) and create a new 1-room room. Resizing rooms is more difficult since we cannot guarantee that the room will be open when the meeting it needs begins. Adding rooms is easier because then this room will always be there; it was not used because we just created it at this stage in the algorithm.

Suboptimal Algorithm Change As noted above, this turned out to be suboptimal, but I keep it here until I can come up with a better alternative.

To take into account the scenario described above, you will need to do additional work at any time when you need to create a new room:

• Find a list of all currently active meetings (including the one you are currently evaluating).
• Start with the largest meeting and schedule each meeting in the room.
• When you reach a meeting that cannot be scheduled, this is the size of the room you must create.

Thus, in the example above, this change comes into play in step 5 when you need to create a new room. Explanation of the step above:

• All currently active meetings: {m2, m3, m4, m5}. To record current numbers: {3, 2, 1}
• Starting from the largest, assign each meeting to the room {m2 goes into 3-room, m5 goes into 2-room, m3 goes into 1-room}
• m4 stuck without a room. Therefore, we must create a place for this. m4 is size 1, so the new room also has size 1.

Answer 4

To find the minimum number and capacity of conference rooms required for all meetings, you first need to schedule these meetings as desired in the rooms (with an evaluation function that minimizes the number of rooms). This is planning (similar to a course schedule ) NP-complete or NP-hard. That means your problem too.

This, in turn, implies that there is no known algorithm for your problem that is optimal and scalable. Greedy algorithms (including your example) will not be optimally optimal (or even not optimal if you have more restrictions) - but at least they will scale :) To get even better results (if necessary), look at optimization algorithms, such as metaheuristics.

Answer 5

 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 6

Here is my java solution.

 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); }