Minimum Number of Bus Stations / Meeting Rooms

Question: At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.

Example: Time table is like below:

Bus         Arrival         Departure 
BusA        0900 hrs        0930 hrs
BusB        0915 hrs        1300 hrs
BusC        1030 hrs        1100 hrs
BusD        1045 hrs        1145 hrs

Then the answer must be 3. Otherwise the bus-station will not be able to accommodate all the buses.

Answer:
Let’s take the same example as described above. Now if we apply dynamic programming and calculate the number of buses at station at any time (when a bus comes or leaves). Maximum number in that pool will be nothing but the maximum number of buses at the bus-station at any time. That number is the minimum number of platforms required.

So first sort all the arrival(A) and departure(D) time in an int array. Please save the corresponding arrival or departure in the array also. Either you can use a particular bit for this purpose or make a structure. After sorting our array will look like this:

0900    0915    1930    1030    1045    1100    1145    1300
A       A       D       A       A       D       D       D

Now modify the array as put 1 where you see A and -1 where you see D. So new array will be like this:

1       1       -1      1       1       -1      -1      -1

And finally make a cumulative array out of this:

1       2       1       2       3       2       1       0

Your solution will be the maximum value in this array. Here it is 3.

I think that code for this will not be complex so I am skipping that part. The complexity of this solution depends on the complexity of sorting.

PS: If you have a arriving and another departing at same time then put departure time first in sorted array.

 

Further Thoughts: You don not need to create a cumulative array or an array with 1 and -1; you just need a counter (cnt) initialized at '0'. Whenever, you find an 'A' in arrival-departure array, increment cnt by 1. Compare it with maximum value (max); if it is greater than max, make max equal to cnt. If you get a 'D' in arrival-departure array, decrement cnt by 1. At the end, return 'max'.

 

Examples:

Input:  arr[]  = {9:00,  9:40, 9:50,  11:00, 15:00, 18:00}
        dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time (time between 11:00 to 11:20)

 

// Returns minimum number of platforms reqquired
int findPlatform(int arr[], int dep[], int n)
{
   // Sort arrival and departure arrays
   sort(arr, arr+n);
   sort(dep, dep+n);
 
   // plat_needed indicates number of platforms needed at a time
   int plat_needed = 1, result = 1;
   int i = 1, j = 0;
 
   // Similar to merge in merge sort to process all events in sorted order
   while (i < n && j < n)
   {
      // If next event in sorted order is arrival, increment count of
      // platforms needed
      if (arr[i] < dep[j])
      {
          plat_needed++;
          i++;
          if (plat_needed > result)  // Update result if needed
              result = plat_needed;
      }
      else // Else decrement count of platforms needed
      {
          plat_needed--;
          j++;
      }
   }
 
   return result;
}

 

Time Complexity: O(nLogn), assuming that a O(nLogn) sorting algorithm for sorting arr[] and dep[].

或者下面这种写法，思路是一样的：

int min_rooms(vector<Interval>& meetings) {
    vector<int> times;
    for(auto m : meetings) {
        times.push_back(m.begin);
        times.push_back(-m.end);
    }   
    sort(times.begin(), times.end(), [](int a, int b){
        return abs(a) == abs(b) ? a < b : abs(a) < abs(b);
    });   
    int ret = 0, cur = 0;
    for(auto t : times) {
        if(t >= 0) ret = max(ret, ++cur);
        else --cur;
    }
    return ret;
}

 

The follow up question:

You have a number of meetings (with their start and end times). You need to schedule them using the minimum number of rooms. Return the list of meetings in every room.

 

The answer:

First we need to realize that randomly schedule meetings to available rooms won’t give you an optimal solution. For example, suppose there are 4 meetings, the (start, end) time are (1, 3), (1, 5), (6, 7), (4, 7). When (1, 3) comes, assign to room A, then (1, 5) comes, assign to room B, then (6, 7) comes, assign to room A as it is available, then (4, 7) comes, both room A and B are not available so we have to assign a new room C for it. However, a better solution is two rooms, room A for meeting (1, 3) (4, 7) and room B for meeting (1, 5) (6, 7).

However, the optimal solution solution is not far from it. If we first sort all the meeting by the start time, then we could just assign them one by one and to the first available room.

The reason is simple, when considering a meeting from s[i] to e[i], as there is no unschedule meeting before s[i], by putting the (s[i], e[i]) meeting in any available room (if there is one) would leads to the same results.

So the code looks like this.

void arrange(vector<pair> meeting) { // the pair contains the start and end time.
  sort(meeting.begin(), meeting.end());
  vector<vector<pair>> room; // for each room, there is a list of meetings.
  for (auto m : meeting) {
    bool found = False;
    for (auto& r : room) {
      if (m.first >= r.back().second) // we can arrange the meeting in the room
        r.push_back(m);
        found = True;
        break;
      }
    }
    if (!found) {
      room.push_back({m});
    }
  }
  cout << "Requires " << room.size() << " rooms" << endl;
  for (int i = 0; i < room.size(); ++i) {
    cout << "Room " << i << endl;
    for (auto m : room[i]) {
      cout << "Meeting: " << m.first << " " << m.second << endl;
    }
  }
}

 

References:

http://tech-queries.blogspot.com/2009/05/number-of-bus-stations.html

http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/

http://www.fgdsb.com/2015/01/30/meeting-rooms/

https://nuttynanaus.wordpress.com/2014/04/26/software-engineer-interview-questions-3/

https://hellosmallworld123.wordpress.com/2014/05/30/arranging-the-meeting-room/