👨‍💻 문제

총 인원의 수가 주어지고
각 인원마다의 시작시간, 종료시간이 주어짐

이 때 필요한 최소 좌석의 수와
각 좌석마다 사용된 횟수를 구하는 문제

---

✍️ 풀이

🧑 인원 별 스케줄

시작 시간이 이른 인원부터 좌석을 사용하도록 한다

// 인덱스 0 : 사용 시작 시간
// 인덱스 1 : 사용 종료 시간
PriorityQueue<int[]> schedules = new PriorityQueue<>((a, b) -> a[0] - b[0]);

🪑 사용 가능한 좌석 번호

각 인원은 가장 낮은 번호의 좌석부터 앉기 때문에 이 또한 빠르게 조회할 수 있도록 우선순위 큐를 사용한다

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

🔚 사용 종료 시간

각 인원이 좌석을 사용하기 시작했을 때, 사용 종료 처리를 빠르게 하기 위해 이 또한 우선순위 큐를 사용한다

// 인덱스 0 : 좌석 번호
// 인덱스 1 : 사용 종료 시간
PriorityQueue<int[]> stopUseWhen = new PriorityQueue<>((a, b) -> a[1] - b[1]);

🔢 좌석 사용 횟수

각 좌석의 사용 횟수를 저장한다

int[] usedCnt = new int[N + 1];

🧠 로직

1. 시작 시간이 이른 인원부터 좌석을 사용한다
2. 해당 인원의 시작 시간 이전까지 사용 종료해야 할 좌석을 사용 종료 처리한다
3. 사용 가능한 좌석이 있는지 확인한다
   3-1. 있다면 해당 좌석을 사용한다
   3-2. 없다면 새 좌석을 추가한다
4. 사용한 좌석과 사용 종료 시간을 저장한다

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class _12764 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<int[]> schedules = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] schedule = new int[2];
            schedule[0] = Integer.parseInt(st.nextToken());
            schedule[1] = Integer.parseInt(st.nextToken());
            schedules.add(schedule);
        }

        int computerCounts = 0;
        int[] usedCnt = new int[N + 1];
        PriorityQueue<Integer> usableComputers = new PriorityQueue<>(); // 사용 가능한 좌석 번호
        PriorityQueue<int[]> stopUseWhen = new PriorityQueue<>((a, b) -> a[1] - b[1]);    // 좌석 번호 및 사용 종료 시간
        while (!schedules.isEmpty()) {
            int[] schedule = schedules.poll();
            int start = schedule[0];
            int end = schedule[1];

            // 사용 시작 시간 이전까지 사용 종료하는 모든 좌석 정리
            while (!stopUseWhen.isEmpty() && stopUseWhen.peek()[1] <= start) {
                int[] stopUsed = stopUseWhen.poll();
                usableComputers.add(stopUsed[0]);
            }

            int computerNum = (usableComputers.isEmpty())
                    ? ++computerCounts          // 빈 좌석이 없으면 PC 추가
                    : usableComputers.poll();   // 있다면 해당 좌석 사용
            usedCnt[computerNum]++;
            stopUseWhen.add(new int[] {computerNum, end});
        }

        // 출력
        StringBuilder sb = new StringBuilder();
        sb.append(computerCounts);
        sb.append('\n');
        for (int i = 1; i <= computerCounts; i++) {
            sb.append(usedCnt[i]);
            sb.append((i == computerCounts) ? '\n' : ' ');
        }
        System.out.print(sb);

    }

}