[백준] 1931번 : 회의실 배정

문제

 

 

접근 방식

DP를 이용해서 O(N^2) 풀이를 생각할 수도 있지만 주어진 입력과 제한 시간으로는

해당 시간 복잡도로는 풀 수 없는 문제다.

 

간단하게 생각해 보면 가장 많은 회의를 배정하기 위해서는

가장 빨리 끝나는 회의들만 골라주면 된다.

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

위의 경우를 예로 들면 첫 번째 회의가 가장 빠른 4시에 끝나니

이 회의를 고른 후에 다음으로 4시 이후에 시작하는 다른 회의를 골라야

가장 효율적으로 회의를 배정할 수 있는 것을 알 수 있다.

1, 4 
3, 5
0, 6
5, 7
3, 8
5, 9
6, 10
8, 11 
8, 12 
2, 13 
12, 14

 

위는 주어진 회의 시간들을 끝나는 시간이 가장 빠른 순으로 정렬하고

끝나는 시간이 같은 경우에는 시작하는 시간이 빠른 순으로 정렬해 준 결과다.

 

정렬한 뒤에 보면 {1, 4}, {5, 7}, {8, 11}, {12, 14}를 선택하는 것이

가장 효율적이라는 것을 더 알기 쉽게 볼 수 있다.

 

즉, 정렬을 수행한 후에 시작 시간이 현재까지 기록된

가장 빠른 끝나는 시간보다 크거나 같은 경우가

다음에 올 수 있는 가장 최적의 회의 배정이므로

반복문을 한 번만 수행하여 회의실을 배정할 수 있다.

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int[][] times = new int[n][2];

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

			times[i][0] = Integer.parseInt(st.nextToken());
			times[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(times, (o1, o2) -> o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0]);

		int min = -1;
		int count = 0;

		for (int i = 0; i < n; i++) {
			if (min <= times[i][0]) {
				count++;
				min = times[i][1];
			}
		}

		System.out.println(count);
	}
}