[백준 1931] - 회의실 배정(JAVA)

출처 -https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

[문제풀이] 

시간에 따라 최대한 많이 배정해야하거나 선택하는 문제를 활동 선택 문제 라고 한다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대 개수를 찾아야한다. 이전의 선택한 회의 결과가 이후에 결과에 영향을 미치지 않게 하려면, 이전 회의 종료시간이 이후의 회의 시작에 겹치면 안된다. 그래서 '종료 시간을 기준으로 문제를 정렬' 하고 

겹치지 않는 활동에 대해 종료시간이 더 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아 진다!

 

Comparator 인터페이스를 사용하여 재정의(Override)를 할 것이기 때문에 인터페이스와 구현 개념을 모르면 다소 어려울 수 있다.  정렬은 한번만 사용하기 때문에 Arrays.sort(정렬대상, 정렬기준(재정의)) 방식으로 사용했다.

아니면 익명객체를 사용하는 방법은 주석처리를 따로 해놨다. 

 

• time[n][0] 회의 시작시간 , time[n][1] 회의 종료시간 2차원 배열을 만든다.
• Comparator를 재정의하여 time[n][1] 회의 종료시간 기준으로 배열을 sort 한다.
• 입력 받은 회의의 수 만큼 for문을 돌린다.
• 이전 종료시간이 다음 시작시간이랑 겹치지 않을때 이전 종료시간에 다음 시작시간의 종료시간을 값을 넣어준다.
• 이때 회의실을 사용할 수 있는 개수를 늘리고 for문이 끝나면 답을 출력한다.

---

[소스코드] 

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		/*
		 * time[][0] = 회의시작시간
		 * time[][1] = 회의종료시간
		 */
		int[][] time = new int[n][2];

		StringTokenizer st;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			time[i][0] = Integer.parseInt(st.nextToken());
			time[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(time, 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]; //회의 종료시간 정렬
			}
		});

//		Arrays.sort(time, comp); //다른 방법

		int count = 0;
		int prev_end_time = 0;

		for (int i = 0; i < n; i++) {
			if (prev_end_time <= time[i][0]) {
				prev_end_time = time[i][1];
				count++;
			}
		}

		System.out.println(count);

	}
// 
//	public static Comparator<int[]> comp = 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];
//		}
//	};
}

-참고 https://st-lab.tistory.com/145 , https://st-lab.tistory.com/243