[백준] 1931번: 회의실배정(그리디, 정렬)

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

1931번: 회의실배정

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		int[][] arr = new int[N][2];	// 회의 별 시작, 종료 시간 저장할 배열
		for(int i=0; i<arr.length; i++) {
			arr[i][0] = scan.nextInt();	// 시작 시간
			arr[i][1] = scan.nextInt();	// 종료 시간
		}
		
		// 종료 시간 순으로 정렬 -> 종료 시간이 같을 경우 시작 시간 순 정렬.
		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] arr1, int[] arr2) {
				if(arr1[1] == arr2[1]) {	// 종료 시간이 같을 경우
					return Integer.compare(arr1[0], arr2[0]);	// 시작 시간 오름차순 정렬
				}
				return Integer.compare(arr1[1], arr2[1]);		// 종료 시간 오름차순 정렬
			}
		});
		
		int maxMeeting = 0;	// 최대 회의 수
		int checkTime = 0;	// 다음 시작 시간과 비교	
		for(int i=0; i<N; i++) {
			if(arr[i][0] >= checkTime) {     // 다음 회의 시작 시간이 이전 회의 종료 시간보다 클 경우
				checkTime = arr[i][1];	 // 다음 종료 시간 변경 
				maxMeeting += 1;         // 회의 +1
			}
		}
		
		System.out.println(maxMeeting);
		scan.close();
	}

}

풀이

각 회의에 대해 시작시간과 종료시간이 주어지고, 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라.

 

위 문제에서 핵심은 다음과 같다.

 

1. 회의의 시작시간과 끝나는 시간이 같을 수도 있다.(1시 ~ 3시) , (3시 ~ 5시)

2. 끝나는 시간이 가장 짧은 것 부터 회의가 겹치지 않게 카운트 해주면 된다.

 

위 2번의 방법을 생각해내는 것이 전부다 ..

처음엔 시작 시간 순으로 정렬 후 종료 시간을 정렬하고, 겹치지 않는 풀이를 생각해 봤지만... 반례가 있었다.

1시~8시, 2시~8시, 3시~4시

위와 같을땐 1시, 2시가 아닌 3시~4시를 선택하는게 더 많은 회의를 할 수 있다.

 

따라서 시작 시간이 아닌 종료 시간을 기준으로 잡고 정렬을하고, 종료 시간이 같으면 시작 시간을 정렬한다.

끝나는 시간이 빠를수록 -> 다음 회의는 일찍 시작한다.

그 후 끝나는 시간 이후로 가장 빨리 시작하는 회의를 선택한다.(시작 시간도 오름차순 정렬)

 

문제의 예제 입력 1을 풀이에 맞게 종료 시간 정렬 -> 시작 시간 정렬을 한 후 출력한 결과다.

(1,4) -> (5,7) -> (8,11) -> (12,14) 를 회의로 하면 회의를 최대 4번 할 수 있다.

 

Java - Comparator 설명