[백준_JAVA_알고리즘] 11000 강의실 배정 #힙 #우선순위 큐

 

강의 시작 시간, 종료 시간을 2차원 배열에 저장합니다.

PriorityQueue는 기본 내림차순 정렬이고, Comparator을 이용해서 오름차순 정렬을 합니다.

람다식을 이용하여 정렬을 할 수도 있습니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());
        int[][] time = new int[N][2];
        int count = 0;

        for (int i = 0; i < N; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            time[i][0] = Integer.parseInt(stringTokenizer.nextToken()); // 시작 시간
            time[i][1] = Integer.parseInt(stringTokenizer.nextToken()); // 종료 시간
        }

        /*
            오름차순 정렬
            Comparator 인터페이스 사용
            또는 람다식 Arrays.sort(time, (a, b) -> a[0] - b[0]);
        */

        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });

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

        for (int[] t : time) {
            while (!priorityQueue.isEmpty() && priorityQueue.peek() <= t[0]) {
                priorityQueue.poll();
            }
            priorityQueue.offer(t[1]);
            count = Math.max(count, priorityQueue.size());
        }

        System.out.println(count);
    }
}

 

Ti ≤ Sj 일 경우 priorityQueue.poll()을 이용해서 큐에서 제거합니다.

while (!priorityQueue.isEmpty() && priorityQueue.peek() <= t[0]) {
    priorityQueue.poll();
}

 

priorityQueue.offer(t)를 통해 현재 진행되는 강의의 종료 시간을 저장합니다. 예를 들어 (1, 3)은 3이 저장됩니다.

priorityQueue.offer(t[1]);

 

priorityQueue.size()를 통해 강의실의 수를 구할 수 있습니다.

count = Math.max(count, priorityQueue.size());

 

 

.

.

.

 

문제는 아래에서 확인할 수 있습니다.

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