[JAVA] 백준 1931번 - 회의실 배정

 

📖 문제

 

📋 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int timeTable[][] = new int[N][2];

		for (int i = 0; i < N; i++) {
			timeTable[i][0] = sc.nextInt();
			timeTable[i][1] = sc.nextInt();
		}
		Arrays.sort(timeTable, (a, b) -> {
			if(a[1] == b[1]) return a[0] - b[0];
			return a[1] - b[1];
		});

//		System.out.println("종료 시간에 맞춰 정렬");
//		for (int i = 0; i < N; i++) {
//			System.out.println(timeTable[i][0] + " " + timeTable[i][1]);
//		}

		int ans = 0;
		int time = 0;

		for (int i = 0; i < N; i++) {
			// 다음회의시작시각 >= 이전회의종료시각
			if (timeTable[i][0] >= time) { 
				time = timeTable[i][1];
				ans++;
			}
		}
		System.out.println(ans);
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

회의 종료시간에 따라 오름차순으로 정렬한 후 회의 종료시간을 업데이트해나가면서 카운트하면 답을 구할 수 있습니다. 그리고 만약 종료시간이 같은 데이터들이 있을 때 시작시간을 빠른 순으로 정렬하지 않는 경우 아래와 같은 반례가 생길 수 있습니다.

3
1 3
4 8
8 8

3
1 3
8 8
4 8

 

 

🔗 링크

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