C# Coding Test Course, Assigning Meeting Rooms

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:

1. First, sort all meetings based on their start and end times.
2. 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.
3. If a new meeting can start, update the end time of the meeting room; otherwise, prepare to use a new meeting room.
4. 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.