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

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

1931번: 회의실 배정

첫번째 시도 - 틀린 답

• 풀이

회의 시간이 짧은 순서대로 정렬한다. 차례대로 회의 시간이 겹치지 않는 회의만 추가한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int arr[][] = new int [N][3];
		int result[] = new int[N];
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = arr[i][1] - arr[i][0];
		}
		for (int i=0; i<N; i++) result[i] = -1;
		
		// 정렬
		Arrays.sort(arr, (a1, a2)->{
			if(a1[2]==a2[2]) return Integer.compare(a1[0], a2[0]); // 회의 길이가 같다면 시작시간 오름차순
			else return Integer.compare(a1[2], a2[2]); // 회의 길이 오름차순
		});

		result[0] = 0; // 선택된 회의 배열
		int cnt = 1; // 선택된 회의 개수
		
		for (int i = 1; i<N; i++) {
			boolean flag = true;
			for (int j = 0; j<N; j++) {
				if (result[j]==-1) break; // 선택된 회의가 더 이상 없다면 break
				
				int tmp = result[j];
				if (arr[i][0]<=arr[tmp][0] && arr[i][1]<=arr[tmp][0]) continue; // 선택된 회의 시간의 시작시간보다 회의 시작 시간, 종료 시간이 작다면 continue
				if (arr[i][0]>=arr[tmp][1] && arr[i][1]>=arr[tmp][1]) continue; // 선택된 회의 시간의 종료시간보다 회의 시작 시간, 종료 시간이 크다면 continue
				flag = false; // 회의 겹침
				break;
			}
			if (flag==true) { // 회의가 겹치지 않는다면
				result[cnt] = i; // 회의 선택
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}

틀렸습니다.

(반례를 못 찾았음)

 

 

두번째 시도 - 정답

• 풀이

회의 종료 시간의 오름차순으로 정렬한다. 차례대로 회의 시간이 겹치지 않는 회의만 추가한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int arr[][] = new int [N][2];
		int result[] = new int[N];
		
		// 회의 시간 입력
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		for (int i=0; i<N; i++) result[i] = -1;
		
		// 정렬
		Arrays.sort(arr, (a1, a2)->{
			if(a1[1]==a2[1]) return Integer.compare(a1[0], a2[0]); // 종료 시간이 같다면 시작 시간 오름차순으로 정렬
			else return Integer.compare(a1[1], a2[1]); // 종료 시간 오름차순으로 정렬
		});
		// Arrays.sort(arr, (a1, a2)-> a1[1]==a2[1] ? a1[0]-a2[0] : a1[1]-a2[1]);
		
		// 첫번째 회의 추가
		int end = arr[0][1]; 
		int cnt = 1;
		
		for (int i = 1; i<N; i++) {
			if (arr[i][0]>=end) { // 회의 종료 시간보다 시작 시간이 같거나 늦다면
				cnt++; // 회의 가능
				end = arr[i][1]; // 회의 종료 시간 변경
			}
		}
		// 정답 출력
		System.out.println(cnt);
	}
}