[1931] 회의실 배정

✔ 회의실 배정

[백준 1931]

문제 분석하기

현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는데 유리하므로

종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택

손으로 풀어보기

1. 회의 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬
   
   • 단, 종료 시간이 같을 때는 시작 시간을 기준으로 다시 한 번 정렬
   • 예) (1, 2), (2, 2)의 경우 (1,2)를 먼저 실행해야 (2, 2)까지 실행 가능함
2. 순차적으로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택

예)
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14 의 경우
정렬을 하면 [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]이 되므로
[1, 4], [5, 7], [8, 11], [12, 14] 로 4개의 회의를 진행하게 됨

슈도코드 작성하기

N(회의 개수) A(회의 정보 저장)
A 배열 정렬 수행하기(종료 시간 기준으로 정렬, 종료 시간이 같으면 시작 시간 기준 정렬)
for(회의실의 개수만큼 반복하기) {
    if(겹치치 않는 다음 회의가 나온 경우) {
        현재 회의의 종료 시간으로 종료 시간 업데이트하기
        진행할 수 있는 회의 수 1 증가
    }
}
총 진행 가능 회의 수 출력하기

코드 구현하기

/**
 * 1931) 회의실_배정
 */
public class D035_1931 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(회의 개수)
        int N = sc.nextInt();
        // A(회의 정보 저장)
        int[][] A = new int[N][2];
        for (int i = 0; i < N; i++) {
            A[i][0] = sc.nextInt();
            A[i][1] = sc.nextInt();
        }
        // A 배열 정렬 수행하기
        // 종료 시간 기준으로 정렬, 종료 시간이 같으면 시작 시간 기준 정렬
        Arrays.sort(A, new Comparator<int[]>() {
            @Override
            public int compare(int[] S, int[] E) {
                if (S[1] == E[1]) {
                    return S[0] - E[0];
                }
                return S[1] - E[1];
            }
        });
        int count = 0;
        int end = -1;
        for (int i = 0; i < N; i++) {
            // 겹치치 않는 다음 회의가 나온 경우
            if (A[i][0] >= end) {
                // 현재 회의의 종료 시간으로 종료 시간 업데이트하기
                end = A[i][1];
                // 진행할 수 있는 회의 수 1 증가
                count++;
            }
        }
        // 총 진행 가능 회의 수 출력하기
        System.out.println(count);
    }
}