🔍 Problem

1931 회의실 배정

---

📃 Input&Output

---

📒 해결 과정

가. 종료시간을 기준으로 정렬

이 문제의 포인트는 겹치지 않는 시간대의 집합을 찾는 것이고, 그 경우는 종료시간을 기준으로 나열하고 찾으면 최대 경우의 수를 구할 수 있다.

"현 시점 기준 빠른 종료시간이 짧은 시간대이다"라는 점을 사용

계속해서 짧은 회의 시간대를 찾아나가는 점에서 "그리디하다" 라고 표현할 수 있다.

나. 빨리 끝나는 거 선택
0초부터 찾아가면되고 만약 종료시간이 같다면 시작시간이 빠른 것부터 회의실에 넣으면 된다?

왜냐하면, (4,4), (1,4)로 정렬이 되어 있다면 (4,4)를 하고 현재 시간이 4이므로 (1,4) 회의를 진행을 못한다. 따라서, (1,4), (4,4) 순으로 회의가 진행되어야 한다.

---

❗ Trouble shooting

가. 종료시간이 같은 경우 고려 안한 문제
해당 문제에서 신경써야할 부분은 다음과 같다.

시작시간과 종료시간이 같은 경우 해당 회의는 시작과 동시에 끝난다.

이 문제는 (1,4), (4,4)를 예시로 들 수 있다. 만약 (4,4)의 회의가 먼저 시작되면 (1,4)의 회의는 진행이 불가능하고 그 반대면 가능하다. 따라서 답의 경우가 각각 2와 1로 달라지는 경우가 생긴다. 이런 상황을 해결하기 위해 위의 경우처럼 회의의 끝나는 시간이 동일한 경우, 시작시간 기준으로 오름차순 정렬한다.

---

💻 Code

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] arr = new int[N][2];

        for (int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }

        Arrays.sort(arr, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int time = 0;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i][0] >= time) {
                time = arr[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

---

🎸 기타

가. Java 2차원 배열 정렬
1. 오름차순

Arrays.sort(arr, (a,b) -> (return 생략) Integer.compare(a[1],b[1]));

2. 내림차순

Arrays.sort(arr, (a,b) -> (return 생략) Integer.compare(b[1],a[1]));

3. 두번째 인자가 같을 경우 첫번째 인자 기준으로 오름차순

Arrays.sort(arr, (a,b) -> {
	if (a[1] == b[1]) {
		return Integer.compare(a[0], b[0]);
		}
	return Integer.compare(a[1], b[1]);
});

---

🤔 느낀점

풀이 방법을 이끌어내는게 쉽지않다.