[ 백준 ] 1931번 - 회의실 배정

NaHyun_kkiimm·2024년 3월 28일

Java 그리디 백준 알고리즘

알고리즘

목록 보기

16/18

문제 요약

한 개의 회의실이 존재하고, 이를 사용하고자하는 N개의 회의에 대하여 최대 사용할 수 있는 회의 최대 개수를 출력하시오.

< 예시 >

[ 입력 ]

[ 출력 ]
4

[ 힌트 ]

(1,4) (5,7) (8,11) (12,14)를 이용할 수 있다.

< 제약 조건 >

첫째 줄엔 회의의 수 N이, 1 ~ N+1까지 줄에는 각 회의의 정보가 주어진다.
회의의 정보는 시작 시간과 끝나는 시간이 주어진다.
회의가 겹쳐선 안 된다.
한번 시작한 회의는 중간에 중단될 수 없으며, 끝나는 동시에 다음 회의가 시작될 수 있다.

< 백준 >

실버 1 / 그리디, 정렬
출처 : https://www.acmicpc.net/problem/1931

풀이

1) 끝나는 시간을 기준으로 정렬한다. 만약 겹칠 경우, 시작 시간이 느린 순(소요 시간이 짧은)으로 정렬한다.
2) 이전에 선택된 회의의 끝나는 시간과 이후에 선택될 회의의 시작 시간이 겹치지 않는다면, 해당 회의를 다음 회의로 선택한다.
3) 카운트를 세면 결과를 도출할 수 있다.

Code

public class BaekJoon1931 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int count = 1;
        int N = Integer.parseInt(bf.readLine());
        int[][] times = new int[N][2];
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(bf.readLine());
            times[i][0] = Integer.parseInt(st.nextToken());
            times[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(times, 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 now = times[0][1];

        for(int i=1;i<N;i++) {
            if (times[i][0] >= now) {
                now = times[i][1];
                count++;
            }
        }

        System.out.println(count);

    }
}