[백준 11000] 강의실 배정 (JAVA)

문제

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

풀이

우선순위큐를 이용하여 해결하였습니다.

들어오는 강의를 시작시간 기준으로 정렬합니다.

강의를 하나씩 넣기 전에 현재 큐에 데이터가 없거나 peek()한 강의의 종료시간이 지금 강의보다 느리면 넣고 아니면 계속 큐에서 값을 꺼냅니다.

큐 크기가 가장 클 때를 출력합니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int ans = 0;

        for (int[] lecture : inputData()) {
            while (!pq.isEmpty() && pq.peek() <= lecture[0]) {
                pq.poll();
            }
            pq.offer(lecture[1]);
            ans = Math.max(pq.size(), ans);
        }

        System.out.println(ans);
    }

    public static int[][] inputData() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[][] input = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(input, (o1, o2) -> {
            if (o1[0] == o2[0]) return o1[1] - o2[1];
            else return o1[0] - o2[0];
        });

        br.close();
        return input;
    }
}