[Java] 백준1931_회의실배정

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

1931번: 회의실 배정

[문제]

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

[입력]

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

[출력]

4

 

[풀이]

그리디 알고리즘의 대표적인 문제이다. 

시작시간보다 종료시간에 초점을 두어 회의실을 배정하였다.종료시간을 기준으로 오름차순 정렬을 하고, 그 다음 배열부터는 종료시간보다 같거나 큰 시작시간을 찾아주었다.여기서 헷갈렸던 것은 회의의 시작시간과 끝나는 시간이 같을 수도 있다라는 조건이였다.현재 종료시간이 3이라고 했을 때, 뒤에 시작-종료시간이 (3,4)인 회의와 (4,4)인 회의가 있다고 가정해보자.(3,4)인 회의를 먼저 배정하면, 바로 뒤에 (4,4)회의를 진행할 수 있지만 반대로 (4,4)회의를 먼저 배정할 경우 (3,4)회의는 진행할 수 없다. 그러므로, 종료시간으로 오름차순정렬을 하되, 종료시간이 같을 경우 시작시간을 기준으로 오름차순을 해야하므로 compareTo 메소드에 삼항연산자를 이용하여 아래와 같이 구현하였다.

 

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

public class BJ1931_회의실배정 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		Meet[] arr = new Meet[N];

		for (int i = 0; i < N; i++) {
			int s=sc.nextInt();
			int e=sc.nextInt();
			arr[i]= new Meet(s,e);
		}
		
		Arrays.sort(arr);
		
		int end=arr[0].end;
		int count=1;
		
		for(int i=1; i<N; i++) {
			if(arr[i].start>=end) {
				count++;
				end=arr[i].end;
			}
		}
		
		System.out.println(count);

	}

	static class Meet implements Comparable<Meet> {
		int start;
		int end;

		public Meet(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Meet o) {
			return this.end != o.end ? this.end - o.end : this.start - o.start;
		}

	}

}