[BOJ/백준] 1931 회의실 배정 (S1)

문제

https://www.acmicpc.net/problem/1931

 

풀이

이 문제에 그리디 알고리즘을 사용해서 풀었다. 최대한 많은 선택을 하기 위해서는 회의실 종료 시간이 빨라야 하고, 이전에 선택한 결과가 이후의 결과에 영향을 미치면 안된다. 

 

즉, 서로 겹치지 않는 회의들에 대하여 종료 시간이 빠르면 더 많은 회의를 선택할 수 있다.

 

따라서 입력받은 회의들을 종료 시간을 기준으로 오름차순 정렬하고, 종료 시간이 같은 회의들은 시작 시간을 기준으로 오름차순 정렬했다.

가장 빨리 끝나는 것은 a1이므로 첫 번째로 a1을 선택하고 a1의 종료 시간을 end에 저장한다. 그리고 end와 이후의 회의 시간의 시작 시간을 바교하여 end <= 회의 시작 시간 중 가장 먼저 있는 회의 시간인 a4를 선택한다. 이 과정을 반복하면 a1 → a4 → a8 → a11이 선택되므로 최대 회의 가능한 수는 4가 된다.

Code

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N= Integer.parseInt(br.readLine());
        int arr[][] = new int[N][2];

        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, new Comparator<int[]>() {  // 서로 겹치지 않는 활동에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다는 것
            @Override
            public int compare(int[] o1, int[] o2) {  // 종료 시간을 기준으로 오름차순
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });

        int cnt = 0;
        int end = 0;
        for (int i = 0; i < N; i++) {
            if (end <= arr[i][0]) {  // 이전 종료 시간이 현재 시작 시간보다 작거나 같으면 cnt늘리고 end 현재 회의의 종료시간 저장
                cnt++;
                end = arr[i][1];
            }
        }
        bw.write(cnt + "");
        bw.flush();
        bw.close();
    }
}