[백준] Gold V. 강의실 배정

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

 

문제 유형

• 정렬
• 우선순위 큐

 

풀이

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

public class boj11000 {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        PriorityQueue<int []> pq = new PriorityQueue<>((a,b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });

        PriorityQueue<Integer> end = new PriorityQueue<>();
        end.add(0);

        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            pq.add(new int[]{a,b});
        }

        while(!pq.isEmpty()) {
            int [] cur = pq.poll();

            if (end.peek() <= cur[0]) {
                end.poll();
            }
            end.add(cur[1]);
        }
        System.out.println(end.size());
    }
}

 

풀이 과정

우선순위 큐를 두개 만들어준다. 

PriorityQueue<int []> pq

• 시작시간, 끝나는 시간을 담는다.
• 오름차순을 해준다.
  • 시작시간이 같다면, 끝나는 시간을 기준으로 오름차순 해준다. ex) (1,2), (1,3) 이런 순서로 정렬해준다.

PriorityQueue<Integer> end

• 끝나는 시간을 담는 우선순위 큐

pq에 담긴 값들을 하나씩 꺼내면서, pq의 시작시간과 end의 값을 비교해준다.

이 때 종료시간이 시작시간보다 크다면, 새로운 강의실을 이용해야 한다.

• ex) (1,3) (2,4)일 때 종료시간 3이 2보다 크므로 새로운 강의실을 이용해야함.

종료시간이 시작시간보다 같거나 작다면, 같은 강의실을 이어서 이용할 수 있다.

• ex) (1,3) (3,5)일 때, 종료시간 3이 시작시간 3과 같으므로 이어서 사용할 수 있다.

 

end에 값인 종료시간 값들은 이렇게 변화할 것이다.

0 -> 3 -> [3,4] -> [4,5] 

결국, 마지막에 end에 담겨있는 종료시간의 수가 강의실의 수를 의미하므로 그대로 출력해주면 된다.