JAVA - 백준 알고리즘 - 1931번 회의실 배정

백준 단계별 풀기에 그리디알고리즘으로 분류되어있는 문제인데, 간단하게 풀릴줄 알았지만 생각보다 시간이 오래 걸렸다.

 

Comparator의 정렬함수를 적절히 구현하여 간단하게 답을 구했다.

 

정렬 방식
1. 끝나는 시간이 같을때  => 시작하는 시간이 이른 순서대로

2. 끝나는 시간이 다를때  => 끝나는 시간이 이른 순서대로

 

1번을 정렬해주는 이유는 시작시간과 끝나는 시간이 같은 경우를 고려해주기 위해서이다.

 

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 P1931 {

	static int N, count, temp;
	static int[][] start;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		start = new int[N][2];
		for (int i = 0; N > i; ++i) {
			String str = br.readLine();
			StringTokenizer st = new StringTokenizer(str, " ");

			start[i][0] = Integer.parseInt(st.nextToken());
			start[i][1] = Integer.parseInt(st.nextToken());
		}
        // 입력
        
		Comparator<int[]> endSort = new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[1] == o2[1]) { // 끝나는 시간이 같을때
					return o1[0] - o2[0]; // 시작시간이 낮은 순서대로 정렬
				} else { // 끝나는 시간이 같으면
					return o1[1] - o2[1]; // 끝나는 시간 순서로 정렬
				}
			}
		};

		Arrays.sort(start, endSort);
		temp = start[0][1];
		count = 1;
		for (int i = 1; N > i; i++) {
			if (start[i][0] >= temp) {
				count++;
				temp = start[i][1];
			}
		}
		System.out.print(count);

	}

}