1931

회의실 배정 : https://www.acmicpc.net/problem/1931

 

 

1. 먼저 끝나는 회의 부터 선택한다.

2. 끝나는 시간이 같은 경우, 늦게 시작하는 회의를 선택한다.

 

 

2번을 고려하지 않는다면 아래의 반례에서 오답을 출력하게 된다.

 

반례 : 

2
1 1
0 1

2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static int[][] arr;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N][2];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr, (t1, t2) -> {
			if ( t1[1] == t2[1])
				return t1[0]-t2[0];
			return t1[1] - t2[1];
		});

		if (DBG) {
			for (int i = 0; i < N; i++) {
				System.out.printf("[%d %d]\n", arr[i][0], arr[i][1]);
			}
		}

		int cnt = 0;
		int endTime = 0;
		for (int i = 0; i < N; i++) {
			if (endTime <= arr[i][0]) {
				cnt++;
				endTime = arr[i][1];
			}
		}
		System.out.println(cnt);

	}

}