[백준 / 골드5] 11000 강의실 배정 (Java)

문제 보기

사용한 것

• 강의의 시작 시간, 끝나는 시간을 담은 Class
• 더 일찍 시작하는 강의, 더 일찍 끝나는 강의실 부터 다루기 위한 PriorityQueue

풀이 방법

• classPQ에 강의의 시작 시간, 끝나는 시간을 입력 받아 Class를 생성하여 넣어준다.
  • 이 때 Class의 우선 순위는 더 일찍 시작하는 강의가 먼저다.
• roomPQ에 0을 넣어주고 (강의실의 끝나는 시간) classPQ가 빌 때까지 poll한다.
• poll한 현재 강의의 시작 시간이 roomPQ의 peek한 시간보다 같거나 뒤에 있으면 해당 강의실을 사용할 수 있으므로 answer 증가 없이 roomPQ를 poll하고 현재 강의의 끝나는 시간을 offer 한다.
• 더 앞에 있는 경우에는 새로운 강의실이 필요하므로 answer을 1 증가시키고 roomPQ에 현재 강의의 끝나는 시간을 offer 한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Class> classPQ = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);
            classPQ.offer(new Class(start, end));
        }

        PriorityQueue<Integer> roomPQ = new PriorityQueue<>();
        roomPQ.offer(0);
        int answer = 1;
        while (!classPQ.isEmpty()) {
            Class c = classPQ.poll();
            if (roomPQ.peek() <= c.start) {
                roomPQ.poll();
                roomPQ.offer(c.end);
            } else {
                answer++;
                roomPQ.offer(c.end);
            }
        }

        System.out.println(answer);
    }
}

class Class implements Comparable<Class> {

    public int start;
    public int end;

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

    @Override
    public int compareTo(Class c) {
        return this.start - c.start;
    }
}