[백준 11000] 강의실 배정(Java)

문제 링크 : https://www.acmicpc.net/problem/11000

이 문제는 그리디 알고리즘과 우선순위 큐를 이용하여 풀 수 있습니다.

최소의 강의실을 사용해서 모든 수업을 가능하게 하려면 가장 빨리 종료하는 강의와 비교해서 종료 시간이 새로운 강의의 시작 시간보다 짧거나 같을 경우 기존 강의실 할당하는 방식으로 진행해야 합니다. 이를 위해서 입력된 강의들을 시작 시간 - 종료 시간 순위의 우선순위로 하여 정렬하는 작업이 필요합니다.

가장 빨리 종료하는 강의를 구하기 위해서 우선순위 큐를 사용합니다. 정렬된 값에서 하나씩 읽어오면서 우선순위 큐의 피크값의 종료 시간보다 가져온 값의 시작 시간이 더 클 경우 우선순위 큐를 poll 하는 방식으로 기존 강의실을 할당합니다. 쉽게 말해 우선순위 큐가 모든 강의실 정보를 담고 있는 자료구조라고 이해하시면 되겠습니다.

다음은 코드입니다.

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

class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Lecture[] lectures = new Lecture[N];
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            lectures[i] = new Lecture(s,t);
        }
        Arrays.sort(lectures);

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<N;i++){
            Lecture curr = lectures[i];
            if(!queue.isEmpty() && queue.peek() <= curr.s) queue.poll();
            queue.add(curr.t);
        }

        System.out.println(queue.size());
    }

    static class Lecture implements Comparable<Lecture>{
        int s;
        int t;

        Lecture(int s, int t){
            this.s = s;
            this.t = t;
        }

        @Override
        public int compareTo(Lecture o) {
            if(this.s == o.s) return this.t - o.t;
            else return this.s - o.s;
        }
    }
}