탐욕법 알고리즘 예제(3). 백준 [1931] 회의실배정

백준[1931] - 회의실배정

탐욕 법을 이용하여 풀이해야 하는 문제이다. 
최대한 많이 회의실을 사용해야 하기 때문에 종료시간이 빠른 일정을 처리하는 게 유리하다. 

그렇기 때문에, 입력을 종료시간을 우선으로 정렬하되 만약 종료시간이 같다면 시작시간이 이른 일정을 우선으로 정렬한다. 
그 후, 차례로 비교해가며 종료시간이 가장 빠른 일정을 우선으로 처리하면서, 그 일정의 종료시간보다 크거나 같은 일정을 다음 일정으로 처리하며 나가면 된다.

 

다음은 Java로 작성한 코드이다.

import java.util.PriorityQueue;
import java.util.Scanner;

public class MeetingRoom {

	public static void main(String[] args) {

		//Pair class 정의
		class Pair implements Comparable<Pair>{
			public Pair(int a,int b) {
				x = a;
				y = b;
			}
			int x,y;
			@Override
			public int compareTo(Pair o) {
				if(y == o.y){
					return x - o.x;
				}
				return y - o.y;
			}

			public String toString() {
				return (x + " " + y);
			}

		}

		//우선순위 큐 
		PriorityQueue<Pair> q = new PriorityQueue<Pair>();
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		Pair[] arr = new Pair[n];

		//입력 및 정렬
		for (int i = 0; i < n; i++) {
			q.add(new Pair(scan.nextInt(), scan.nextInt()));
		}
		for (int i = 0; i < n; i++) {
			arr[i] = q.poll();
		}

		//기저 조건 설정
		int current = -1 ;
		int count = 0;

		//계산 
		for (int i = 0; i < n; i++) {
			if(arr[i].x >= current) {
				count++;
				current = arr[i].y;
			}
		}

		System.out.println(count);
	}

}

시작시간과 종료시간을 입력받아야 하기 때문에 Pair라는 class를 만들었다. Coparable를 구현하여 비교 가능하게 한다.
앞서 말했듯이 종료시간을 우선으로 그 다음에는 시작시간을 기준으로 정렬한다. 

정렬을 함으로써 탐욕법의 원리를 적용시킬 수 있다.
즉, 다음 일정을 선택해야 하는 상황에 최적의 선택을 할 수 있게 해 준다.