[11000] 강의실 배정

✔ 강의실 배정

[백준 11000]

코드 구현하기

/*
 * 문제 분석하기
 * : 빨리 시작하는 수업부터 배정하도록 함. 만약 수업이 겹칠 경우 강의실을 하나 증가시킴
 */

/* 
 * 손으로 풀어보기
 * 1. 수업에 따른 강의실 배정 준비하기
 * 2. 강의 시작 시간을 기준으로 정렬. 만약 시작 시간이 같을 경우 종료 시간이 빠른 순으로 정렬
 * 3. 앞 수업의 종료 시간보다 다음 수업의 시작 시간이 빠를 경우 강의실을 증가시켜주도록 함
 * 4. 사용할 수 있는 최소 강의실의 개수 출력
 */

/*
 * 11000) 강의실_배정
 */
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int N;
    static Class[] classes; // classes(수업 정보를 담은 배열)
    static PriorityQueue<Integer> pq; // pq(수업 종료 시간을 담을 우선순위 큐)

    /*
     * Class(수업 정보를 담은 클래스)
     */
    static class Class implements Comparable<Class> {
        int start;
        int end;

        public Class(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Class o) {
            if (this.start != o.start) {
                return Integer.compare(this.start, o.start);
            }
            return Integer.compare(this.end, o.end);
        }
    }

    /*
     * 수업에 따른 강의실 배정 준비하기
     */
    static void init(StringTokenizer st) throws IOException {
        N = Integer.parseInt(st.nextToken());

        classes = new Class[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            classes[i] = new Class(start, end);
        }
    }

    /*
     * 수업 정렬하기
     */
    static void sortClasses() {
        Arrays.sort(classes);
    }

    /*
     * 수업 시간에 따라 강의실 배정하기
     */
    static void selectClasses() {
        pq = new PriorityQueue<Integer>();
        pq.add(classes[0].end);
        for (int i = 1; i < N; i++) {
            Class c = classes[i];
            if (c.start >= pq.peek()) {
                pq.poll(); // 다음 수업의 시작 시간이 이전 수업의 종료 시간보다 뒤일 경우, 같은 강의실에서 수업이 가능하므로 이전 수업을 제거하고 다음 수업을 넣어줌
            }
            pq.add(c.end); // 다음 수업의 시작 시간이 이전 수업의 종료 시간보다 앞일 경우, 같은 강의실에서 수업이 불가능하므로 이전 수업을 놔두고 다음 수업을 넣어줌
        }
    }

    /*
     * 최소 강의실의 개수 출력
     */
    static void print() {
        System.out.println(pq.size());
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        init(st);
        sortClasses();
        selectClasses();
        print();
    }
}