This course explains step-by-step how to solve the meeting room assignment problem using C#. The meeting room assignment problem enhances algorithmic thinking and is a common topic in various coding tests.
Problem Definition
Given the start and end times of meetings, each meeting has a specific start and end time, and they cannot occur simultaneously. The problem is to find the minimum number of meeting rooms required to accommodate all given meetings.
Input
The first line contains the number of meetings N. (1 ≤ N ≤ 105)
The next N lines contain the start time start and end time end of each meeting, separated by a space. (0 ≤ start < end ≤ 106)
Output
Print the number of meeting rooms required.
Example
Input Example:
3
0 30
5 10
15 20
Output Example:
2
Approach to Problem Solving
To solve this problem, you can use the following approach:
- First, sort all meetings based on their start and end times.
- Check each meeting in sequence and compare it with the end time of the currently used meeting room to determine if a new meeting can start.
- If a new meeting can start, update the end time of the meeting room; otherwise, prepare to use a new meeting room.
- Finally, return the number of meeting rooms used.
C# Code Implementation
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static void Main() {
int n = int.Parse(Console.ReadLine());
List<(int start, int end)> meetings = new List<(int start, int end)>();
for (int i = 0; i < n; i++) {
var parts = Console.ReadLine().Split(' ');
int start = int.Parse(parts[0]);
int end = int.Parse(parts[1]);
meetings.Add((start, end));
}
// Sort meeting times based on end time
meetings.Sort((a, b) => a.end.CompareTo(b.end));
// Variable to count the number of meeting rooms
int roomCount = 0;
PriorityQueue minHeap = new PriorityQueue(); // Using priority queue
foreach (var meeting in meetings) {
// If the current meeting's start time is greater than or equal to the end time of the meeting room that ends first
if (minHeap.Count > 0 && minHeap.Peek() <= meeting.start) {
minHeap.Dequeue(); // Reuse meeting room
}
// Use a new meeting room
minHeap.Enqueue(meeting.end, meeting.end);
}
roomCount = minHeap.Count; // Number of remaining meeting rooms
Console.WriteLine(roomCount);
}
}
Explanation
The above algorithm is generally classified as a greedy algorithm. It checks the currently ending meeting rooms while processing each meeting to use the minimum number of meeting rooms. A priority queue is used to efficiently manage the currently used meeting rooms. This algorithm derives the optimal result through the following procedure:
Time Complexity Analysis
The main Time Complexity of the algorithm is O(N log N). This is the time required to sort the list of meetings. The subsequent process of checking each meeting takes O(N), resulting in a total time complexity of O(N log N).
Space Complexity Analysis
The space complexity is O(N). This is due to storing meeting information in the list and the priority queue.
Conclusion
In this course, we explored the solution to the meeting room assignment problem using C#. By solving this problem, we learned the appropriate use of greedy algorithms and the efficient use of priority queues. There may be various meeting room assignment problems, so practice solving more problems to improve your skills.