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

백준 1931 회의실 배정

문제

---

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

입력

---

첫째 줄에 회의의 수 N(1<=N<=100,000),
둘째 줄부터 N+1번째 줄까지 각 회의의 정보(회의의 시작 시간, 끝나는 시간)가 공백을 상에 두고 주어진다.

출력

---

첫째 줄에 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

---

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

예제 출력 1

---

4

풀이

회의가 겹치지 않으려면 이전 회의의 종료 시간이 다음 회의의 시작시간보다 작거나 같아야 한다. 그러므로 최대한 많은 회의를 진행하기 위해서는 이전 회의를 빠르게 종료하고 다음 회의를 시작해야 한다. 따라서 입력을 종료 시간을 기준으로 정렬하고(Comparator 활용), 종료 시간 이후에 시작하는 회의를 차례로 선택하면 최대한 많은 회의를 진행할 수 있다.

코드

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =null;
		
		int n = Integer.parseInt(br.readLine());
		int[][] nums = new int[n][2];
		
		for(int i =0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			nums[i][0] = Integer.parseInt(st.nextToken());
			nums[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 종료 시간을 기준으로 회의 정렬
		Arrays.sort(nums, 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];
			}
		});
		
		int cnt =0;					// 회의 개수 카운팅
		int nE =0;					// 이전 회의의 종료 시간 
		
		for(int i=0; i<n; i++) {			
			if(nE<=nums[i][0]) {	// 이전 회의 종료 시간 이후에 시작하는 회의이면 ?
				cnt++;				// 진행시켜 !
				nE = nums[i][1];	// 이전 회의 종료 시간 갱신
			}
		}
		System.out.println(cnt);
	}
}