[백준,BOJ 1931] 회의실 배정(JAVA 구현)

-풀이

  처음 이 문제를 풀 때는 각 회의 정보를 시작시간을 기준으로 정렬하여 회의별 소요되는 시간이 가장 짧은 순서대로 조건을 걸어 카운팅을 하려 했지만, 조건이 애매해져 다른 분의 글을 참고하였다. 다른 분의 글에서는 정렬을 종료시간을 기준으로 하여, 가장 일찍 끝나는 회의 순서대로 카운팅 하는 방법을 사용했다.

 

  맞다. 회의실을 가장 많이 돌리려면, 빨리 끝나는 순서대로 집어넣는 것이 그리디라고 할 수 있다.

 

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

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		// 회의의 수 
		int n = in.nextInt();
		
		int cnt = 0;
		
		// 회의 정보
		int a[][] = new int[n][2];
	
		for(int i=0;i<n;i++) {
			a[i][0] = in.nextInt();
			a[i][1] = in.nextInt();
		}
		
        // 종료시간 기준 정렬
		Arrays.sort(a,new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1] == o2[1])
					return Integer.compare(o1[0],o2[0]);
				
				return Integer.compare(o1[1], o2[1]);
			}
			
		});
				
		int end = 0;
		
		for(int i=0;i<n;i++) {	
			// 직전 회의 종료시간 <= 현재 회의 시작시간이면 회의가 가능하므로,
			if(end<=a[i][0]) {
				// 현재 회의의 종료시간을 갱신 후,
				end = a[i][1];
				// 회의 수 증가.
				cnt++;
			}
			
		}
		
		System.out.println(cnt);
		in.close();
	}

}