[백준] 1931번 - 회의실 배정

 

그리디 알고리즘을 이용한 문제이다. 이러한 문제를 푸는 방식을 '활동 선택 문제'라고 한다. 활동 선택 문제에 대해 간략한 설명은 아래 링크를 참고하면 된다.

https://ddamdoo.tistory.com/159

탐욕법 - 활동 선택 문제(Activity Selection Problem)

 

이 문제를 활동 선택 문제로 풀게되면 먼저 종료시간 순으로 오름차순하고, 만약 종료시간이 같은 경우 시작시간을 기준으로 오름차순을 진행하여 해결하면 된다.

 

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

public class p1931 {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int a = Integer.parseInt(br.readLine());

		int[][] ary = new int[a][2];

		for (int i = 0; i < a; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			ary[i][0] = Integer.parseInt(st.nextToken());
			ary[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(ary, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				if (a[1] == b[1]) {
					return a[0] - b[0];
				}
				return a[1] - b[1];
			}
		});
		int n = 0;
		int cnt = 0;
		for (int i = 0; i < a; i++) {
			if (ary[i][0] >= n) {
				cnt++;
				n = ary[i][1];
			}
		}
		System.out.println(cnt);
	}
}