[알고리즘] 백준 1931 자바 JAVA 그리디 알고리즘 회의실배정

 

 

 

이 목표는 가장 많은 강의 수를 구하는 문제인데, 곰곰히 생각해보면 제일 먼저 따져야할 것은 끝나는 시간이 가장 빠른 것을 기준으로 정하면 되는 문제이다. 다만 중요한 점은 정말 당연한 이야기이지만 다음 강의의 시작시간이 현재 강의의 끝 시간보다 커야한다는 점이다. 왜? 강의는 겹칠 수가 없으니까.

 

문제에는 정렬되어서 나온다는 말이 없기 때문에 정렬을 해야한다. 기준은 끝나는 시간을 기준으로 정렬을 하되, 만약 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬을 하면 된다. 이에 대한 정렬 코드는 아래의 코드이다.

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

		return Integer.compare(start[1], end[1]);
	}
});

 

전체 코드 :

public class BaekJoon_17_1931 {

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());
		int[][] arr = new int[n + 1][2]; // 0:시작 시간, 1:끝 시간

		StringTokenizer st;
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(reader.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}

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

				return Integer.compare(start[1], end[1]);
			}
		});

		int count = 0;
		int end_time = Integer.MIN_VALUE;
		for (int i = 1; i <= n; i++) {
			int start_time = arr[i][0];
			if (start_time >= end_time) {
				end_time = arr[i][1];
				count++;
			}
		}

		writer.write(count + "");

		writer.flush();
		reader.close();
		writer.close();
	}
}