백준 [자바 java] 11000 : 강의실 배정

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

11000번: 강의실 배정

문제설명

n이 주어지고, n개의 강의들이 모두 강의가 가능하게 하도록 준비해야하는 최소 강의실 수를 구하는 문제이다.

 

풀이설명

 

 처음에는 강의실을 2차원 배열에 입력받고, 시작시간을 기준으로 오름차순 한 후, visit 한 배열이 없을 때까지 배열을 처음부터 끝까지 반복해서 확인하는 방법으로 풀었는데, 시간초과가 나왔다.

 문제에 사용된 알고리즘을 확인 한 결과, 우선순위 큐를 사용해야 한다는 것을 알게 되었다.

• 기존 방법과 같이 시작시간을 기준으로 오름차순 정렬한다.
• 우선순위 큐를 만들고 가장 첫번째에 있는 강의의 끝나는 시간을 우선순위 큐에 넣는다.
• 이후 배열의 처음부터 끝까지 하나씩 확인하며 시작시간이 우선순위큐의 가장 앞부분보다 크거나 같으면 큐를 poll한다. (큐의 가장 앞에 있는 시간이 차지하고 있는 강의실을 쓴다고 생각하면 된다)

 

풀이 코드

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


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[][] 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());
        }

        int room = 0;

        int[] vis = new int[n];

        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }else {
                    return o1[0] - o2[0];
                }
            }
        });

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

        q.offer(arr[0][1]);

        for(int i = 1;i<n;i++){
            if(arr[i][0] >= q.peek()){
                q.poll();
            }
            q.offer(arr[i][1]);
        }

        System.out.println(q.size());

    }
}