BOJ 11000 강의실 배정

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

문제

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

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

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

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

---

입력

첫 번째 줄에 N이 주어진다. $(1 ≤ N ≤ 200,000)$

이후 N개의 줄에 $S_i, Ti$가 주어진다. $(0 ≤ S_i < T_i ≤ 10^9)$

---

출력

강의실의 개수를 출력하라.

---

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

---

코드

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

public class Main {
    static class Class implements Comparable<Class> {
        int start, end;

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

        // 우선순위 큐에서 시작 시간이 빠른 수업부터 꺼내기 위함
        @Override
        public int compareTo(Class c) {
            return this.start - c.start;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Class> queue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            queue.offer(new Class(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // 빠르게 수업이 끝나는 순으로 강의실을 뽑기 위한 큐
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        rooms.offer(queue.poll().end);
        while (!queue.isEmpty()) {
            Class check = queue.poll();
            // 사용 중인 강의실 중 가장 빨리 종료되는 수업 시간 이후에 시작하는 수업에 강의실을 배정할 경우
            // 가장 빨리 수업이 종료되는 강의실을 poll 한 뒤, 이후에 시작하는 수업의 종료시간을 offer 해 강의실을 배정
            if(rooms.peek() <= check.start) rooms.poll();
            // 만약 현재 사용 중인 강의실들의 종료시간이 강의실을 배정하려는 수업의 시작시간보다 늦을 경우
            // 새로운 강의실을 배정
            rooms.offer(check.end);
        }

        System.out.println(rooms.size());
    }
}