[BOJ] 1374번 강의실 (Java)

백준 1374 강의실

비슷한 문제인 회의실 배정과는 접근 방법이 달랐다. 회의의 갯수를 최대로 맞춰야 하는 회의실 배정과 달리, 강의실 문제는 모든 회의를 가능하도록 하는 강의실 갯수의 최솟값이었다.

백준 1931 회의실 배정
그렇기 때문에 회의가 종료하는 시간을 기준으로 잡았던 회의실 배정과 달리 강의실은 시작하는 시간을 기준으로 정렬하고 우선순위 큐에 강의실이 끝나는 시간을 넣고 가장 빨리 끝나느 시간에도 강의가 불가능하면 새로운 값을 넣는 식으로 해결했다.

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

public class Main {

    public static void main(String[] args) {
        try {
            int n, e, t, s;
            int [] tmp;
            PriorityQueue <int[]> pq1 = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            PriorityQueue <Integer> pq2 = new PriorityQueue<>();
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(br.readLine());
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                t = Integer.parseInt(st.nextToken());
                s = Integer.parseInt(st.nextToken());
                e = Integer.parseInt(st.nextToken());
                pq1.add(new int[] {t, s, e});
            }
            pq2.add(0);
            while (!pq1.isEmpty()) {
                tmp = pq1.poll();
                e = pq2.poll();
                if (e <= tmp[1]) {
                    pq2.add(tmp[2]);
                } else {
                    pq2.add(e);
                    pq2.add(tmp[2]);
                }
            }
            System.out.println(pq2.size());
        } catch (Exception e) {
        }
    }
}