[백준] 1374: 강의실 JAVA

접근

백준 11000 강의실 배정과 비슷한 문제다. 우선 입력값을 시작 시간이 빠른 순서, 시작 시간이 같다면 종료 시간이 빠른 순서대로 정렬하도록 우선순위큐에 1차적으로 저장했다. 그 다음엔 이제 최소의 강의실의 개수를 구해야 하는데, 여기서 우선순위큐를 하나 더 사용했다. 이 classRoom 큐에는 각 강의실이 몇시까지 사용되는지를 저장한다. 만약 가장 작은 값이 현재 강의의 시작 시간보다 작다면 해당 강의실에서 연강이 가능한 것이고, 아니라면 새로운 강의실 배정이 필요한 것이다. 따라서 모든 계산을 완료한 후 큐의 크기가 곧 필요한 강의실의 최소 개수가 된다. 

 

코드

package week10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ1374 {
    static class Lecture implements Comparable<Lecture>{
        int lectureNum, from, to;

        public Lecture(int lectureNum, int from, int to) {
            this.lectureNum = lectureNum;
            this.from = from;
            this.to = to;
        }

        @Override
        public int compareTo(Lecture o) {
            if(this.from != o.from)
                return this.from - o.from;
            else
                return this.to - o.to;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Lecture> pq = new PriorityQueue<>();

        // 입력값 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            int lectureNum = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            pq.add(new Lecture(lectureNum, from, to));
        }

        // 최소 강의실 계산
        PriorityQueue<Integer> classRoom = new PriorityQueue<>();
        classRoom.add(0);

        while(!pq.isEmpty()){
            Lecture cur = pq.poll();
            int minEndTime = classRoom.peek();

            if(cur.from < minEndTime) classRoom.add(cur.to);
            else { // 해당 강의실에서 수업할 수 있음
                classRoom.poll();
                classRoom.add(cur.to);
            }
        }

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