[백준] 1374 - 강의실

1. 문제

1374번: 강의실

2. 개요

N개의 강의의 강의 번호, 시작 시각, 종료 시각이 주어진다.

최대한 적은 강의실을 이용하고자 할 때 사용하는 강의실의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

강의를 시작 시간, 끝나는 시간의 오름차순으로 정렬한다.

강의를 하나씩 탐색하며 강의실을 갱신한다. 이 때, 강의실은 우선순위 큐(최소 힙)를 이용한다.

강의가 끝나는 시간을 강의실에 넣어준다. 새 강의를 탐색할 때, 강의실의 최솟값과 비교하여 갱신해준다. 가장 빨리 강의가 끝나는 시간보다 새 강의가 일찍 시작한다면 새 강의실에 넣어주는 것이고, 이보다 늦게 시작한다면 해당 강의실의 끝나는 시간을 새 강의의 끝나는 시간으로 바꿔준다.

3-2. Python

import sys
import heapq

N = int(sys.stdin.readline())

lectures = []
rooms = []

for i in range(N):
    lectures.append(list(map(int, sys.stdin.readline().split())))

lectures.sort(key = lambda x : (x[1], x[2]))

for l in lectures:
    if len(rooms) > 0 and rooms[0] <= l[1]:
        heapq.heappop(rooms)
        heapq.heappush(rooms, l[2])

    else:
        heapq.heappush(rooms, l[2])

print(len(rooms))

3-3. C#

internal class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());

        List<int[]> lectures = new List<int[]>();

        for (int i = 0; i < N; i++)
        {
            int[] l = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            lectures.Add(l);
        }

        lectures = lectures.OrderBy(x => (x[1], x[2])).ToList();

        PriorityQueue<int, int> rooms = new PriorityQueue<int, int>();

        foreach (int[] lecture in lectures)
        {
            if (rooms.Count > 0 && rooms.Peek() <= lecture[1])
            {
                rooms.Dequeue();
                rooms.Enqueue(lecture[2], lecture[2]);
            }

            else
                rooms.Enqueue(lecture[2], lecture[2]);
        }

        Console.WriteLine(rooms.Count);
    }
}