백준 11000 자바 - 강의실 배정

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

11000번: 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

코드

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static Lecture[] lectures;
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        lectures = new Lecture[n];
        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            lectures[i] = new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(lectures, (lec1, lec2) -> lec1.start == lec2.start ? lec1.end - lec2.end : lec1.start - lec2.start);

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(lectures[0].end);

        for (int i = 1; i < n; i++) {
            if (queue.peek() <= lectures[i].start) {
                queue.poll();
            }
            queue.offer(lectures[i].end);
        }

        bw.write(String.valueOf(queue.size()));
        bw.flush();
    }
    private static class Lecture {
        int start;
        int end;

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

풀이

입력받아 Lecture객체의 배열로 저장한다. lectures 배열을 정렬을 먼저 수행한다. 시작 시간이 같지 않으면 시작 시간으로, 아니라면 끝나는 시간으로 오름차순 정렬을 수행한다. 그 후 우선순위 큐에 맨 첫 강의의 끝나는 시간을 집어 넣는다. (이때 우선순위 큐는 오름차순으로 정렬을 기본으로 한다.) 그 후, 그 다음 강의의 시작 시간이 큐의 끝나는 시간이 가장 빠른 강의보다 늦은 시간에시작하면 큐의 top(끝나는 시간이 가장 빠른 강의)를 하나 빼고, 큐에 다음 강의의 끝나는 시간을 넣는다. (이 작업은 결국 큐의 크기가 동일하게 유지된다. 같은 강의실에 강의를 배정하는 것이다.) 다음 강의의 시작 시간이 큐의 끝나는 시간이 가장 빠른 강의보다 빠르게 시작하면 빼내는 작업을 하지 않는다. (새로운 강의실을 배정하는 것이다. 큐의 크기가 +1 된다.) 그렇게 반복문을 다 돌은 후, 큐의 크기를 출력하면된다.