C++ Coding Test Course, Assigning Meeting Rooms

Problem Description

There are N meetings that need to be conducted, each with a start time and an end time.
How can we assign meeting rooms to maximize the number of meetings?
In other words, an algorithm needs to be implemented to assign meeting rooms such that the meetings do not overlap.

Input: A list is given containing the start and end times of each meeting.
For example, there can be a list like [(0, 30), (5, 10), (15, 20)].

Output: Print the maximum number of meetings that can be scheduled.

Approach to the Problem

This problem is a typical greedy algorithm problem.
First, sort the meetings based on their end times,
then use the approach of proceeding with the meeting that ends the quickest and selecting the next meeting accordingly.

This way, we can make optimal meeting assignments without overlaps.
A meeting can only be conducted if its start time is greater than or equal to the end time of the previous meeting.

Step-by-Step Solution Process

1. Receive all meeting information.
2. Sort the meetings based on their end times.
3. Initialize a variable to count the maximum number of meetings.
4. Iterate through the meetings and add them if possible.
5. Print the total number of meetings that can be scheduled.

C++ Code Implementation

#include 
#include 
#include 

using namespace std;

// Structure for meeting information
struct Meeting {
    int start;
    int end;
};

// Function to sort meetings based on their end times
bool compare(Meeting m1, Meeting m2) {
    return m1.end < m2.end;
}

// Function to assign meeting rooms
int maxMeetings(vector &meetings) {
    // Sort based on end times
    sort(meetings.begin(), meetings.end(), compare);
    
    int count = 0;
    int lastEndTime = 0;

    for (const auto &meeting : meetings) {
        if (meeting.start >= lastEndTime) {
            // Proceed with the meeting
            count++;
            lastEndTime = meeting.end; // Update the last end time
        }
    }

    return count;
}

int main() {
    vector meetings = {{0, 30}, {5, 10}, {15, 20}};
    
    int result = maxMeetings(meetings);
    
    cout << "Maximum number of meetings that can be assigned: " << result << endl;
    return 0;
}
    

Explanation for Each Step

First, we use a structure to store the start and end times of the meetings.
An important point in greedy algorithms is that we need to sort each meeting by their end times.

After sorting, we use a loop to check each meeting.
If the start time of the current meeting is greater than or equal to the end time of the previous meeting,
we can conduct this meeting, so we increase the count and update the last end time.

After checking all meetings, the final counted value will be the maximum number of meetings that can be scheduled.

Test Cases

We can create several test cases to test the above code.

vector test1 = {{1, 3}, {2, 5}, {4, 6}}; // Expected result: 2
vector test2 = {{1, 10}, {2, 3}, {4, 5}, {6, 8}}; // Expected result: 3
vector test3 = {{1, 2}, {3, 4}, {5, 6}}; // Expected result: 3
    

You can execute each test case and compare it with the expected results
to verify if the code is functioning correctly.

Conclusion

In this tutorial, we learned how to solve the problem of assigning meeting rooms using C++.
We understood how the greedy algorithm provides an optimal solution and demonstrated that by considering
the start and end times of various meetings, we can schedule the maximum number of meetings.

I encourage you to understand and apply this algorithm to solve more complex problems.
Developing a habit of solving various algorithm problems will improve your coding skills.