[골드5, 우선순위 큐] 백준 11000 - 강의실 배정 (자바)

Think

1. 처음에는 되게 단순하게 풀었음. 강의실을 다루기위해 연결리스트를 사용하고, 해당 리스트를 탐색하면서 강의의 시작보다 강의실의 종료시간이 빠르면 갱신하는 식으로.

2. 하지만 틀렸고, 문제를 다시 읽어보면서 반례를 찾아봄

3. 1번처럼 풀면, 최적화되지 않음 (강의가 5-6이고, 강의실에 (3-5, 2-4)로 되어있는 경우일때, 두번째 강의실에 갱신해야 더 최적일 수도 있음)

4. input과 강의실을 관리하는 자료구조들을 정렬해야 될 필요성을 느끼고 우선순위 큐를 활용하였음.

5. (참고) 강의실을 관리하는 우선순위 큐는 끝나는 시간만 저장해도 된다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class test {
    static int N;

    static Lecture[] lectures;
    static PriorityQueue<Lecture> classRoom;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();
        process();
        print();
    }

    private static void print() {
        System.out.println(classRoom.size());
    }

    private static void process() {

        for (Lecture l : lectures) {

            if (classRoom.isEmpty()) {
                classRoom.add(l);
                continue;
            }

            Lecture earlyEndLecture = classRoom.peek();

            // 강의실을 새로 배정해야하는 경우, (현재 진행하는 강의 중 이어서 할 수 있는 강의실이 없는 경우)
            if (earlyEndLecture.end <= l.start) {
                classRoom.poll();
            }

            classRoom.add(l);
        }
    }

    public static void init() throws IOException {
        classRoom = new PriorityQueue<>(new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                return o1.end - o2.end;
            }
        });

        N = Integer.parseInt(br.readLine());
        lectures = new Lecture[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());

            lectures[i] = new Lecture(start, end);
        }

        Arrays.sort(lectures, new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                if (o1.start != o2.start) {
                    return o1.start - o2.start;
                }

                return o1.end - o2.end;
            }
        });
    }


    public static class Lecture {
        int start;
        int end;

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

}