백준 1931번: 회의실 배정

풀이코드

import java.io.*;
import java.util.*;

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));

        int N = Integer.parseInt(br.readLine());

        int[][] time = new int[N][2];

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }

        // 끝나는 시간을 기준으로 오름차순 정렬
        // 만약 종료 시간이 같으면, 시작 시간을 기준으로 오름차순 정렬
        Arrays.sort(time, (o1, o2) -> {
            return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
        });

        int end = 0;
        int count = 0;

        // 각 회의에 대해서, 끝나는 시간이 이전 회의의 끝나는 시간보다 크거나 같으면 선택
        for (int i = 0; i < N; i++) {
            if (end <= time[i][0]) {
                end = time[i][1];
                count++;
            }
        }

        bw.write(String.valueOf(count));
        bw.close();
        br.close();
    }
}

 

 

 

회의 시간 정렬

주된 정렬 기준은 끝나는 시간이고, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬합니다. 이렇게 정렬된 배열에서 가장 빨리 끝나는 회의를 먼저 선택할 수 있도록 합니다.

Arrays.sort(time, (o1, o2) -> {
    return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
});

 

그리디 알고리즘을 이용한 회의 배정

end는 이전 회의가 끝나는 시간을 추적하는 변수입니다. 각 회의를 살펴보면서 end보다 시작 시간이 늦거나 같으면 해당 회의를 배정하고, end를 그 회의의 종료 시간으로 갱신합니다.

int end = 0;
int count = 0;
for (int i = 0; i < N; i++) {
    if (end <= time[i][0]) {  // 끝나는 시간보다 시작 시간이 빠르면 회의 배정 가능
        end = time[i][1];  // 끝나는 시간을 갱신
        count++;  // 회의 배정 개수 증가
    }
}

 

 

시간 복잡도

Arrays.sort()는 O(N log N)의 시간 복잡도를 가집니다.