[BJ1931] 회의실 배정

 백준 - 회의실 배정 

문제 링크

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

1931번: 회의실 배정

 

문제 입출력

2
0 1
3 3

2

 

문제 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
	static int ans, N;
	static Node[] arr;


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

		N = Integer.parseInt(br.readLine());

		// 초기화
		ans = 1;
		arr = new Node[N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());

			arr[i] = new Node(s, e, e - s);
		}

		// 우선, 끝시간을 기준으로 정렬
		// 끝시간이 같다면 시작시간 순으로 정렬
		Arrays.sort(arr, (e1, e2) -> e1.e == e2.e ? e1.s - e2.s : e1.e - e2.e);

		// 그리디
		solution();

		// 출력
		System.out.println(ans);

	} // end main


	private static void solution() {
		int idx = 1;
		Node prev = arr[0];

		while (idx < N) {
			Node cur = arr[idx];

			// 만약 다음 회의로 넘어갈 수 있다면
			if (prev.e <= cur.s) {
				prev = cur;
				ans++;
			}

			idx++;
		}

	} // end solution


	static class Node {
		int s, e;
		int len;


		public Node(int s, int e, int len) {
			super();
			this.s = s;
			this.e = e;
			this.len = len;
		}


		@Override
		public String toString() {
			return "Node [s=" + s + ", e=" + e + ", len=" + len + "]";
		}

	} // end Node
}

그리디를 이용해서 푸는 문제.

종료 시간을 기준으로 정렬하고, 만약 끝 시간이 같다면 시작 시간이 빠른 순으로 정렬.

그 이유는 종료 시간으로 정렬해야, 어느 회의가 빨리 끝나는지 알 수 있다.  주어진 회의 시간을 좁게 좁게 쓰는 것이 관건이기 때문.

종료 시간이 같을 때, 시작 시간 순으로 정렬하는 이유는

 

예를 들어,

2
3 3
2 3

이라는 input 이 있다고 가정하자.

이럴 때, 종료 시간으로만 정렬하면 (3, 3) -> (2, 3) 으로 첫번째 회의의 종료시간 보다 두번째 회의의 시작시간이 빨라서 카운팅을 할 수 없다. 하지만 종료 시간이 같을 때, 시작 시간 순으로 정렬을 하면 (2, 3) -> (3, 3) 으로 카운팅을 할 수 있게 된다. 

 

 

 

 

 

 

 

 

#백준 회의실 배정 이유 #백준 회의실배정 java #bj 회의실 배정 정렬 이유 # bj 회의실 배정 다른 예제

---