Software Engineer Interview Questions (3)

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