[BOJ] 1931번 : 회의실 배정 (JAVA/자바)

문제

---

알고리즘 고민

처음에는 DP 인가 그리디인가 조금 헷갈렸다. 시작하는 시간이랑 끝나는 시간 두개의 변수가 있어 단순 그리디로 풀리는건가 싶었다.

조금 더 고민을 하던 중 최대 할 수 있는 회의의 개수는 결국 끝나는 시간이 낮은 걸 우선순위로 체크하면 된다는걸 깨달았다. 시작하는 시간이야 어떻든지 끝나는 시간이 빨라야 다음 회의가 더 많이 시작할 수 있는 기회가 생기는 것이기 때문이다.

1. 회의의 시간을 끝나는 시간 기준으로 정렬했다. 다만 시간이 같다면 시간이 더 빨리 시작하는 것을 우선적으로 처리하였다. (시간이 같을때 더 빨리 시작하는 것을 우선적으로 해야하는 이유는 회의가 5시에 끝났다고 가정해보자 그 다음으로 6 to 6 과 5 to 6이 있다면 5 to 6 을 진행하고 6 to 6을 진행하면 회의를 2개 더 진행할 수 있지만, 6 to 6 이 먼저 회의가 시작해버리면 5 to 6 은 시작할 수 없다.)

2. 이후 진행된 회의 중 마지막으로 끝난 시간을 계속 기록하며 시작 시간이 끝난 시간 이상이라면 회의를 진행했다 생각하고 끝난 시간을 갱신해주며 count 해준다.

---

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

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

        Arrays.sort(conf, (arr1, arr2) -> {
            if (arr1[1] == arr2[1]) return arr1[0] - arr2[0];
            return arr1[1] - arr2[1];
        });

        int lastTime = conf[0][1], cnt = 1;
        for (int i = 1; i < conf.length; i++) {
            if (lastTime <= conf[i][0]) {
                lastTime = conf[i][1];
                cnt++;
            }
        }

        System.out.println(cnt);
    }
}