[JAVA] 백준 11000 회의실 배정

 

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

 

문제분석

여러 개의 회의가 주어질 때, 하나의 회의실에서 서로 겹치지 않게 진행할 수 있는 회의의 최대 개수를 구하는 문제이다. 각 회의는 시작 시간과 종료 시간으로 이루어져 있으며, 한 회의가 끝나는 시간과 다음 회의의 시작 시간이 같을 경우에는 이어서 진행할 수 있다. 회의들은 임의의 순서로 주어지므로, 가능한 한 많은 회의를 배정하기 위해 회의가 끝나는 시간이 빠른 순서대로 선택하는 그리디 전략을 사용한다. 먼저 모든 회의를 종료 시간 기준으로 오름차순 정렬하고, 이전에 선택한 회의의 종료 시간 이후에 시작하는 회의만 선택하면서 개수를 증가시키면, 하나의 회의실에서 진행할 수 있는 최대 회의 수를 구할 수 있다.

코드

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 종료 시간 추가
        int[][] arr = new int[N][2]; // [[시작시간, 종료시간]..]
        StringTokenizer st;
        int count = 1; // 강의실은 최소 1개 사용하기 때문에, count = 1
        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, (a, b) -> a[0] - b[0]);

        for(int i = 0; i < N; i++){
            int s = arr[i][0];
            int t = arr[i][1];
            if(pq.isEmpty()){ // 비어있다면, 종료 시간 추가
                pq.offer(t);
            }else{
                if(pq.peek() <= s){ // 현재 가장 빨리 끝나는 강의 이어서 i번째 강의 시작 가능한 경우 -> count 안올림
                    pq.poll();
                }else{
                    count += 1;
                }
                pq.offer(t);
            }
        }
        
        
        System.out.println(count);
    }
}