[백준] 19598: 최소 회의실 개수 - JAVA

in Algorithm on 자료 구조

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

풀이

회의의 시작, 종료 시간이 주어지고 최의실을 배정해야 한다.

회의실의 개수를 최소로 해야한다.

시작시간 순으로 정렬을해서 차례대로 회의실에 집어넣었다.

우선순위큐에 종료시간을 넣고, 우선순위큐의 peek이 새로 들어갈 회의의 시작시간보다 작다면 그 방을 사용할 수 있다.

메모리: 48764KB

시간: 668ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {

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

        int[][] arr = new int[N][2];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return Integer.compare(o1[1], o2[1]);
                }
                return Integer.compare(o1[0], o2[0]);
            }
        });

        PriorityQueue<Integer> room = new PriorityQueue<>();
        room.add(arr[0][1]);
        int cnt = 1;
        for (int i = 1; i < N; i++) {
            if (room.peek() <= arr[i][0]) {
                room.poll();
            } else {
                cnt++;
            }
            room.add(arr[i][1]);
        }

        System.out.println(cnt);
    }

}