알고리즘 챌린지 7일차

문제

문제: 백준 알고리즘 1931번 회의실 배정

코드

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int ans=0;
        int ary[][] = new int[N][2];
        for (int i = 0; i < N; i++) {
            ary[i][0] = scan.nextInt();
            ary[i][1] = scan.nextInt();
        }

        Arrays.sort(ary, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1]==o2[1]){   //종료 시간이 같을 때
                    return o1[0]-o2[0];
                }
                return o1[1]-o2[1];
            }
        });
        int end=-1;
        for(int i=0;i<N;i++){
            if(ary[i][0]>=end){     //겹치지 않는 다음 회의가 나온 경우
                end=ary[i][1];      //종료시간 업데이트
                ans++;
            }
        }
        System.out.print(ans);
    }
}

풀이

1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다. 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하다. 그렇기 때문에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택해야 한다.

• 회의 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬한다. 단,종료 시간이 같을 때는 시작 시간을 기준으로 다시 한번 정렬한다.
• 순차적으로 탐색하다가 시간이 겹치지 않는 회의가 나오면 선택한다.

후기

종료 시간이 같을 때, 시작 시간을 기준으로 다시 한번 정렬하는 것이 이 문제의 포인트이다. 이러한 디테일을 놓치지 않도록 주의하자!