백준 1931번 회의실 배정

1931번 회의실 배정

문제

난이도

• Silver 1

알고리즘 분류

• 그리디 알고리즘
• 정렬

풀이

회의실 배정 문제는 가장 빨리 끝나는 회의를 우선적으로 배정해야한다.

2차원 배열에서 원하는 기준으로 정렬을 하기 위해 compare 메서드 사용

코드

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        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]; // 시작 시간 기준으로 정렬
                }
                return o1[1] - o2[1]; // 끝나느 시간 기준으로 정렬
            }
        });
        int time = 0; // 현재 시간
        int cnt = 0; // 회의 개수

        for (int i = 0; i < n; i++) {
            if(arr[i][0] >= time) { // 시작 시간이 현재 시간 이후 일 때 
                cnt++;
                time = arr[i][1];
            }
        }
        bw.write(cnt + "");
        bw.close();        
    }
}