백준 19598. 최소 회의실 개수

 

문제(링크)

문제 풀이

 회의의 시작시간 순으로 정렬을 한 리스트와 끝나는 시간을 기준으로 한 우선순위 큐를 사용하여 풀었습니다.

 먼저 정렬한 하나 씩 탐색하면서 우선순위 큐의 가장 먼저 끝나는 시간과 회의 시작 시간을 검사하여 회의 시작 시간보다 가장 먼저 끝나는 시간이 더 작거나 같으면 회의가 종료된 거기 때문에 우선순위 큐에서 빼준다.

 다음 우선순위 큐에 탐색한 회의 끝 시간을 넣어 준 후 우선순위 큐에 최대 사이즈를 확인하면 최소 회의실을 구할 수 있다. 

소스 코드(Java)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 최소 회의실 개수
 * https://www.acmicpc.net/problem/19598
 */
public class baek19598 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        List<int[]> list = new ArrayList<>();

        //회의시간이 가장 빠르게 끝나는 순으로 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        });

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list.add(new int[]{start, end});
        }

        //회의시작 시간이 빠른 순으로 정렬
        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });

        //첫번째 회의가 끝나는 시간 pq에 넣고, 회의실 1개 부터 계산
        pq.offer(list.get(0)[1]);
        int answer = 1;

        for (int i = 1; i < N; i++) {
            while (!pq.isEmpty() && pq.peek() <= list.get(i)[0]) {
                pq.poll();
            }
            pq.offer(list.get(i)[1]);
            answer = Math.max(answer, pq.size());
        }

        System.out.println(answer);
    }
}