[백준] 11000번: 강의실 배정 - java

문제

https://www.acmicpc.net/problem/11000

 

접근법

문제를 처음 봤을 땐 먼저 수업을 정렬해야겠다고 생각했다.

시작 시간 순으로 정렬을 한 뒤, 현재 수업이 들어갈 강의실을 찾으면 된다.

현재 수업이 들어갈 강의실은 앞 수업들의 종료 시간을 비교하면 된다.

 

현재 사용 중인 강의실들의 종료 시간을 저장한다.

저장된 강의실의 종료 시간 중 가장 먼저 끝나는 강의실과 현재 수업의 시작 시간을 비교해 해당 강의실을 사용할지, 추가로 강의실을 사용할지 결정한다.

 

왜 가장 먼저 끝나는 강의실만 비교하면 될까?

가장 먼저 끝나는 강의실을 현재 수업에서 사용할 수 없다면 더 늦게 끝나는 강의실 역시 사용할 수 없기 때문이다

 

코드

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

public class Main {

    static int N;
    static PriorityQueue<Class> pq = new PriorityQueue<>();
    static PriorityQueue<Integer> rooms = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        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());
            int S = Integer.parseInt(st.nextToken());
            int T = Integer.parseInt(st.nextToken());
            pq.offer(new Class(S, T));
        }

        rooms.offer(pq.poll().T); // 첫 번째 강의가 끝나는 시간
        while (!pq.isEmpty()) {
            Class c = pq.poll();

            if (rooms.peek() <= c.S) {
                rooms.poll();
            }

            rooms.offer(c.T);
        }

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

    static class Class implements Comparable<Class> {
        int S, T;

        public Class(int S, int T) {
            this.S = S;
            this.T = T;
        }

        @Override
        public int compareTo(Class c) {
            if (this.S == c.S) {
                return this.T - c.T;
            }

            return this.S - c.S;
        }
    }
}