[백준] 1931 회의실 배정

www.acmicpc.net/problem/1931

1931번: 회의실 배정

처음에는 시작 시간을 기준으로 정렬하여 맨 처음부터 끝까지 반복해서 돌면서 회의 종료시간보다 크거나 같은 회의 갯수를 세주어 가장 갯수가 많은 것이 답이 되도록 생각했지만 그렇게 하면 시간초과가 나기 때문에 잘못 생각한 방법이었습니다.

 

문제 풀이 :

그리디 알고리즘으로 이전 종료시간과 이후 시작 시간이 겹치지 않으면서 가장 종료시간이 빠른 것을 선택해 세주면 됩니다.

1. 먼저 종료 시간을 기준으로 정렬합니다. 

2. 다음 시작 시간이 종료 시간보다 크거나 같으면 종료 시간을 갱신해주고 count 변수로 세줍니다.

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[][] arr = new int[N][2];
		int count = 0, end = 0;

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < 2; j++) {
				arr[i][j] = sc.nextInt();
			}
		} // end of input

		Arrays.sort(arr, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[1]==o2[1]) return o1[0]-o2[0];
				return o1[1]-o2[1];
			}
		});
		

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

}

참고자료 : st-lab.tistory.com/145