💔11000 강의실

 

 

1. 문제 설명

11000번: 강의실 배정

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

www.acmicpc.net

강의의 시작 시간과 종료 시간이 주어졌을 때 해당 강의들을 전부 소화할 수 있는 최소 강의 수를 구하여라.

2. 푸는 원리

저번에 풀었는데 틀렸다. 틀리는 방법도 똑같았다 ㅜㅜ. 다시 푸는 방법을 정리해 보겠다.

1. 배열 혹은 List에 강의 시작 시간이 빠른 순으로 강의를 정렬한다.
2. 강의의 끝 시간을 기준으로 값들을 정리하는 Priority Queue를 만든다.

자 이제 List에 존재하는 값들을 차례로 순회할 것이다. 우리가 현재 조회하는 강의를 A라고 해보자. A의 강의 시작 시간이 오후 1시라고 할 때, 현재 시각을 오후 1시라고 가정하는 것이다. 이렇게 list에서 현재 조회 중인 강의의 시작 시간을 ‘현재 시각’이라고 가정하겠다. List는 시작 시간이 빠른 순으로 정리 되어있으므로, 우리는 시간의 경과에 따라 강의들을 차례로 조회하게 될 것이다. PQ는 ‘현재 시각’에 진행하고 있는 강의들이 담겨져있다. 따라서 PQ의 Size는 현재 진행 중인 강의의 개수이다. PQ의 원소 하나 하나를 강의실이라 생각하는 편이 좋다. 예를 들어 설명하겠다.

1. 만약 PQ가 Empty라면 현재 조회 중인 강의를 넣고, 다음 강의를 조회한다.
2. 만약 PQ에 강의가 존재한다면, PQ는 강의를 종료시간이 빠른 순으로 정렬했을 것임으로, PQ.peek()은 현재 PQ에 담긴 강의 중 종료 시간이 제일 빠른 강의 이다. 만약 PQ.peek()의 종료시간보다 현재 조회 중인 강의 A의 강의 시작 시간이 늦다면! PQ.peek()에 해당하는 강의는 ‘현재 시각’에서 끝난 강의임으로 PQ에서 poll()한다. (즉 강의실에서 나간다.)
3. 이렇게 (현재시각 ≥ 강의의 종료 시간)인 PQ 속 강의는 모두 poll 하다가 처음으로 (현재 시각 ≤ 강의의 종료 시간)인 강의를 만나면 현재 조회 중인 강의 A를 PQ 속에 넣는다.
4. 이제 PQ 속은 ‘현재시각’에 강의 중인 강의들만 들어가 있다. 이때의 PQ의 Size 즉 강의실의 개수를 센다.
5. 이렇게 모든 list 속 강의를 순회하고, 지금까지 나왔던 강의실 사용 개수 중 최대 개수를 출력한다.

3. 코드 분석

Copy

import java.util.*;
import java.io.*;

public class Main{

    static int N;

    static int maxQsize = 0;

    public static void main(String[] args) throws  IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        Lecture2 [] list = new Lecture2[N];

        // 값 입력 받기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end= Integer.parseInt(st.nextToken());

           list[i] = new Lecture2(start, end);
        }

        // 시작 순으로 정렬
        Arrays.sort(list, Comparator.comparingInt(o -> o.start));



        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < list.length; i++) {
            Lecture2 now = list[i];

            if(pq.isEmpty()){
                pq.offer(now.end);
            }
            else{
                int Qsize = pq.size();

                for (int j = 0; j < Qsize; j++) {
                    if(now.start >= pq.peek()) pq.poll();
                    else{
                        pq.add(now.end);
                        break;
                    }
                }

                maxQsize = Math.max(maxQsize, pq.size());
            }
        }

        System.out.println(maxQsize);

    }
}

class Lecture2 {
    int start;
    int end;

    public Lecture2 (int start, int end) {
        this.start = start;
        this.end = end;
    }
}