백준 1374번 - 강의실

문제

백준 1374번 - 강의실

아이디어

• 강의실을 최대한 적게 사용하기 위해서는 강의 시간이 겹치는 것을 최소화 해야 유리하다.
• N개의 강의 정보를 입력받고 시작 시간 순으로 정렬한다. 정렬하는 이유는 끝나는 시간만을 고려하기 위해서다.
• 우선순위큐를 준비해 시작 시간 순으로 정렬된 강의의 종료 시간을 차례대로 삽입한다.
• 그러다가 우선순위큐에서 꺼낸 시간, 즉 가장 빨리 끝나는 강의의 종료 시간보다 현재 강의의 시작 시간이 크거나 같을 경우, 새 강의실 대신 끝나는 강의실을 사용하면 되므로 큐에서 하나 제거해준다.
• 모든 강의에 대해 반복하고 최종적으로 우선순위큐에 남은 강의들 개수가 정답이 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N log N)

코드 구현

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 BJ_1374 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][2];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            arr[num - 1][0] = start;
            arr[num - 1][1] = end;
        }

        //시작 시간 순 정렬
        Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);

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

        for (int[] c : arr) {

            //현재 강의 시작 전에 끝나는 강의가 있다면 해당 강의실을 사용하면 된다.
            if (!qu.isEmpty() && qu.peek() <= c[0]) {
                qu.poll();
            }

            //강의 종료 시간 저장
            qu.offer(c[1]);
        }

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