[BOJ] 11000 강의실 배정

강의실 배정

풀이

• S[i]에 시작해서 T[i]에 끝나는 N개의 수업이 주어진다. 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 함.

• 앞서 풀었던 회의실 배정 문제랑 비슷한 듯 하지만, 모든 수업을 가능해야 한다 라는 조건이 다르다.

• 이 조건 때문에, 2차원 배열로 시작시간, 끝나는 시간을 담고 시작하는 시간이 빠른 순으로 정렬을 해준다. (Comparator 사용)

• 그 다음 우선순위 큐를 이용하는데, 우선순위 큐에는 회의가 끝나는 시간을 넣을 것이다.

  • 우선순위 큐를 이용하는 이유는, 회의가 끝나는 시간들을 넣었을 때 빨리 끝나는 순으로 poll 할 수 있도록 정렬이 되기 때문에 사용한다.

• 배열의 첫번째 원소의 끝나는 시간을 넣고 시작한다. for문을 순회하면서, 배열의 원소의 시작 시간이 우선순위 큐의 peek 한 원소 보다 늦으면(크면), 같은 강의실에서 할 수 있으므로, 끝나는 시간을 갱신할 수 있다.

  • 우선순위 큐에서 poll하고, 지금 보고 있던 배열 원소의 끝나는 시간을 넣어준다.

• peek한 원소보다 현재 보고 있는 배열 원소의 시작 시간이 작다면, peek한 원소와 같은 회의실에서 진행할 수 없으므로 끝나는 시간을 갱신할 수 없다.(=다른 회의실에서 진행해야 함.)

  • 우선순위 큐에 지금 보고 있던 배열 원소의 끝나는 시간을 offer.

• for문으로 배열을 다 순회한 뒤, 우선순위큐 size를 구하면 그것이 정답(=필요한 회의실 수)

🙆‍♀️ 정답 코드

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        StringTokenizer st;
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr,new Comparator<int[]>(){
                    @Override
                    public int compare(int[] o1, int[] o2){
                        if(o1[0]==o2[0]) return Integer.compare(o1[1],o2[1]);
                        return Integer.compare(o1[0],o2[0]);
                    }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(arr[0][1]);
        for(int i=1;i<N;i++){
            if(arr[i][0]>=pq.peek()){
                pq.poll();
                pq.offer(arr[i][1]);
            }
            else{
                pq.offer(arr[i][1]);
            }
        }
        System.out.println(pq.size());
    }
}

• 우선순위큐를 생각도 못해서 너무 어려웠다. 다음에 다시 풀어보zr 🤧