[그리디/우선순위 큐] 백준 11000 강의실 배정 풀이

 [백준]  Gold5 - 강의실 배정_11000

문제

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

11000번: 강의실 배정

풀이 방법

이거 푸는데 최소 3시간 이상은 잡힌 것 같다.. 처음에 문제를 잘못보고 강의를 최대한 많이 듣는 횟수를 알아내라는 것인줄 알았는데, 계속 틀려서 다시 읽어보니 최소한의 강의실 갯수를 구하는 문제였다. 처음에 잘못된 접근법은 회의실 배정 문제처럼 종료시간을 기준으로 오름차순으로 정렬후 풀었으나, 이러면 값은 안구해진다.

시작시간으로 정렬 후 PriorityQueue를 사용해서 최소 시간이랑 강의 종료시간이랑 각각 비교후에 강의 종료시간이 최소 시간이랑 같거나 큰경우 q.poll하고 다시 add하는 방식으로 진행했으며, 최소 시간보다 작은경우에는 add만 진행하는 방식으로하고, 결국 마지막 pq에 남은것들이 필요한 강의실 갯수가 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws IOException {
        int max = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] room = new int[n][2];
        boolean[] visited = new boolean[n];
        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) {
                if (o1[0] == o2[0]) {
                    return (o1[1] - o2[1]);
                }
                return (o1[0] - o2[0]);
            }
        });
        PriorityQueue<Integer> q = new PriorityQueue<>();
        q.add(room[0][1]);
        for(int i = 1; i < n; i++){
            if(q.peek() <= room[i][0])
                q.poll();
            q.add(room[i][1]);
        }
        System.out.println(q.size());
    }
}