[1931번] 회의실배정

문제 기출 : [https://www.acmicpc.net/problem/1931]

 

 

풀이 방법

[그리디알고리즘] 접근   여러가지 풀이 방법이 떠올랐다. 한참 이 문제를 풀 때 쯤에 Comparator와 Comparable을 연습하고있던 찰나여서 생각나는대로 작성했다.   2차원 배열에 입력 값을 저장 -> sort (끝나는 시간 기준, 같으면 시작시간 기준) -> 끝나는 시간을 체크해가면 카운팅 -> 마지막 카운트 값을 출력   참고로 더 간단하게 풀이도 가능하다. 우선순위 큐를 생각해보면 답이 나올 것이다.

 

문제 풀이

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			int N = Integer.parseInt(br.readLine());
			int[][] time = new int[N][2];

			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");

				for (int j = 0; j < 2; j++) {
					time[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			Arrays.sort(time, new Comparator<int[]>() {
				@Override
				public int compare(int[] arg0, int[] arg1) {
					if (arg0[1] == arg1[1]) {
						return arg0[0] - arg1[0];
					} else {
						return arg0[1] - arg1[1];
					}
				}
			});

			int end = -1;
			int count = 0;

			for (int i = 0; i < N; i++) {
				if (time[i][0] >= end) {
					end = time[i][1];
					count++;
				}
			}

			System.out.println(count);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}