[BOJ] 11000 강의실 배정 - JAVA

1. 문제

11000번: 강의실 배정

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!

---

2. 풀이

1.  강의 시작, 끝 시간을 int[]로 만들어서 우선순위 큐에 넣는다. 이 때, 정렬 순서는 강의 시작시간 오름차순이다.(같으면 종료시간 오름차순)

2.  Integer 우선순위 큐 end를 만들어서 첫번째 강의 종료시간을 넣어두고 강의 하나씩 탐색을 시작한다. (answer은 1부터 시작)

3.  가장 첫 번째 요소가 현재 강의 시작시각보다 이르거나 같으면 한 강의실을 쓸 수 있다. end에서 하나 뽑고 다시 현재 강의 종료시각을 넣는다.

4.  가장 첫 번째 요소가 현재 강의 시작시각보다 느리다면 한 강의실을 쓸 수 없다. end에 현재 강의 종료시각을 넣고 answer++한다.

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

public class BOJ_11000_강의실배정 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->{
         if(o1[0]==o2[0]) return o1[1]-o2[1];
         else return o1[0]-o2[0];
      });
      StringTokenizer st;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         queue.offer(new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
      }

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

      //첫번째 강의
      end.offer(queue.poll()[1]);
      int answer = 1;

      int[] now;
      while(!queue.isEmpty()){
         now = queue.poll();
         if(end.peek()<=now[0]){
            //강의 가능
            end.poll();
            end.offer(now[1]);
         }else{
            //불가능
            end.offer(now[1]);
            answer++;
         }
      }

      System.out.println(answer);
   }

}

---

3. 결과

끝나는 시각 저장을 ArrayList로 한 뒤 이분탐색해서 풀었는데, 우선순위 큐를 사용해서 맨 앞만 비교해도 된다는 사실을 깨달았다.