[BAEKJOON] 1931번 회의실 배정

---

이차원 배열에 회의 시작시간과 종료시간을 저장한다.

이전 회의의 종료 시간과 이후 회의의 시작 시간이 서로 겹치지 않으면 된다.

또한, 최대한 많은 회의를 진행하려면 종료시간이 빠른 것을 선택한다.

 

예제 입력의 회의 시작 시간과 종료 시간

문제의 힌트에서 보이는 바와 같이 총 회의는 4번으로 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

위의 그래프와 같이 종료시간을 기준으로 정렬하고, 다음 회의는 시작 시간이 같을 경우 회의시간이 짧은 것을 우선으로 선택하면 된다.

Comparator 인터페이스를 구현하여 입력되는 값의 종료 시간을 기준으로 오름차순 정렬한다. 즉, 종료시간이 작을 수록 앞쪽에 배치된다.

 

(Comparator 인터페이스 사용법을 아직 모른다면 아래 글 참조해주세요)

2022.03.13 - [JAVA] - [JAVA] Comparable과 Comparator

[JAVA] Comparable과 Comparator

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cnt = 0;
		int arr[][] = new int[N][2];
		StringTokenizer st;

		for (int k = 0; k < N; k++) {
			st = new StringTokenizer(br.readLine(), " ");
			arr[k][0] = Integer.parseInt(st.nextToken());
			arr[k][1] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] a1, int[] a2) {
				// 종료 시간이 같은 경우
				if (a1[1] == a2[1]) {
					return a1[0] - a2[0]; // 시작 시간이 빠른 순으로 정렬
				}
				return a1[1] - a2[1]; // 그렇지 않다면 종료 시간이 빠른 순으로 정렬
			}

		});
		int prev_end_time = 0;

		for (int i = 0; i < N; i++) {
			// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신
			if (prev_end_time <= arr[i][0]) {
				prev_end_time = arr[i][1];
				cnt++;
			}
		}

		System.out.println(cnt);
	}
}

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

1931번: 회의실 배정