[백준] 11000: 강의실 배정 JAVA

접근

이 문제 역시 1946번과 같이 제한 시간 내에 풀기 위해서는 O(N^2)이 되면 안된다. 강의실의 개수를 최소로 사용하기 위해서는 최대한 많은 수업이 연속해서 일어나야 한다. 즉, 최대한 (앞 수업의 종료 시간) <= (뒷 수업의 시작 시간)이 되도록 만들어야 한다.

우선 수업 시간의 시작 시간이 가장 빠른 순서대로, 만약 시작 시간이 같다면 종료 시간이 빠른 순서대로 정렬한다. 그 뒤에 앞선 수업들의 종료시간 중 가장 빨리 끝나는 값과  현재 수업의 시작 시간을 비교하면 된다. (우선순위 큐를 사용한다는 의미) 모든 연산이 종료되고 나면, pq의 사이즈값이 곧 사용하는 강의실의 최소 개수가 된다. 

 

(1, 2), (1, 7), (2, 4), (5, 6) 총 4개의 강의가 있다고 해보자. 결론부터 말하면 (1, 2)~(2, 4)~(5, 6) / (1, 7) 으로 총 2개의 강의실을 사용하게 된다. 

 

먼저 첫 강의는 무조건 빈 강의실에 배정될 수 있으므로, 해당 종료 시간이 그대로 pq에 들어간다. 

(1, 2), (1, 7), (2, 4), (5, 6) 

endTime(pq): 2

 

두 번째 강의의 경우, 앞선 강의의 종료시간보다 시작시간이 빠르기 때문에 같은 강의실을 사용할 수 없다. 따라서 해당 강의의 종료 시간을 pq에 넣어준다.

(1, 2), (1, 7), (2, 4), (5, 6) 

endTime(pq): 2, 7

 

세 번째 강의의 경우, pq에서 꺼낸 값이 2로 시작 시간과 동일하므로 같은 강의실을 사용할 수 있다. 2값을 빼고 이어서 진행되는 수업의 종료 시간을 넣는다. 

(1, 2), (1, 7), (2, 4), (5, 6) 

endTime(pq): 4, 7

 

마지막 강의의 경우, pq에서 꺼낸 값이 4로 시작 시간인 5보다 작기 때문에 같은 강의실을 사용할 수 있다. 4를  빼고 6을 넣어준다.

(1, 2), (1, 7), (2, 4), (5, 6) 

endTime(pq): 6, 7

 

모든 계산을 마치고 나면, 처음에 예시와 함께 보았던 강의실의 마지막 수업 종료 시간과 pq에 들어있는 값이 일치하게 된다. 즉, pq의 사이즈가 곧 필요한 강의실의 개수가 되는 것을 확인했다. 

 

코드

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

public class BJ11000 {
    static class Table implements Comparable<Table>{
        int s, t;

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

        // 시작 시간이 빠른 순서대로, 같다면 빨리 끝나는 순으로 정렬
        @Override
        public int compareTo(Table o) {
            if(this.s == o.s)
                return this.t - o.t;
            else return this.s - o.s;
        }
    }

    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<Table> tables = new PriorityQueue<>();

        // 입력값 저장
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            tables.add(new Table(s, t));
        }

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

        while (!tables.isEmpty()){
            Table cur = tables.poll();
            int earliestEndTime = pq.peek();

            if(cur.s >= earliestEndTime) pq.poll();
            pq.add(cur.t);
        }

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