BOJ 11000 - 강의실 배정(Java)

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

11000번: 강의실 배정

 

풀이

우선순위 큐를 이용 

강의실 시작시간 기준 오름차순 정렬 후 탐색/비교

    - 큐의 첫 번째 요소만 비교하면 강의실 추가 유무를 확인 가능 

    - queue.peek()(마감 시간) <= 현재 탐색 요소의 강의 시작시간 -> 같은 강의실로 할당 가능

    - queue.peek()(마감 시간) > 현재 탐색 요소의 강의 시작시간 -> 같은 강의실로 할당 불가능, 새로운 강의실 필요

 

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

public class Main {
    static int N;
    static int[][] room;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N=Integer.parseInt(br.readLine());
        room= new int[N][2];

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

        Arrays.sort(room, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[0]);
            }
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(room[0][1]);
        for(int i=1;i<N;i++){
            if(pq.peek()<=room[i][0]){
                pq.poll();
            }
            pq.offer(room[i][1]);
        }
        System.out.println(pq.size());
    }
}