[백준 11000] - 강의실 배정(JAVA)

[문제] 

 

출처 - https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

---

[문제풀이] 

 

언뜻 회의실 배정(1931) 문제와 똑같다고 생각하여 종료시간 기준으로 정렬한 뒤 풀었으나 틀렸습니다. 그 이유는 최대한 많이 강의실을 배정할 수 있게 만드는 게 아니라 최소의 강의실을 사용한다 가 포인트입니다.

한 강의가 시작되고 끝나는 시간에 최대한 강의를 시작할 수 있게 만들어야 강의실을 최대한 적게 쓸 수 있습니다.

 

예를들어 아래와 같이 수업이 주어집니다.(시작시간 기준 정렬함)

 

1   5

2   3

4   9

5   8

 

우선 첫 번째 수업을 진행하기 위해서 강의실(1개)을 배정합니다.

 

두 번째 수업을 진행해야 하는데 아직 첫 번째 수업이 끝나지 않아서 강의실을 추가로 배정합니다. (2개)

 

4시에 시작하는 세 번째 수업을 진행해야 합니다. 아직 첫 번째 수업은 끝나지 않았고 두 번째 수업은 끝나 있습니다.

 

첫 번째 수업보다 우선 수업이 끝난 두 번째 뒤에 진행을 한다면 강의실을 추가하지 않아도 됩니다.

 

마지막 수업을 진행하려 합니다. 세 번째 수업은 진행 중이고 첫 번째 수업이 우선 끝났으니 해당 강의실에 배정합니다.

 

그러면 최소한의 강의실(2개)을 사용해서 모든 수업을 가능하게 할 수 있습니다.

즉, 수업 시작 순으로 정렬한 뒤 순차적으로 끝나는 시간을 우선순위 큐에 넣어준다면 문제를 해결할 수 있습니다.

 

---

[소스코드] 

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

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());

        int[][] time = new int[n][2];

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }

        //시작시간 오름차순 정렬
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(time[0][1]);
        for(int i=1; i<n ;i++){
            if(pq.peek() <= time[i][0]){
                pq.poll();
            }
            pq.add(time[i][1]);
        }

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