[JAVA] 백준 11000번 강의실 배정

문제

11000번: 강의실 배정

입력

• 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
• 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

• 강의실의 개수를 출력하라.

입력 예제

3
1 3
2 4
3 5

출력 예제

2

문제 풀이

• 회의시간을 입력받은 후, 시작 시간이 빠른 순, 마치는 시간이 빠른 순으로 정렬
• 맨 처음 강의가 끝나는 시간을 pq에 넣기
• 이후 강의들을 탐색하면서, 이전에 끝난시간보다 시작하는 시간이 작거나 같다면, pq에 있는 peek값을 빼주기 -> 강의실을 추가하지 않아도 되므로 !
• 위 과정을 마쳤다면, 현재 탐색한 강의의 끝나는 시간을 pq에 넣기
• 모든 강의를 탐색했다면 pq에 남아있는 값들의 수가 정답 !!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class boj11000 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		// 회의시간 입력
		int arr[][] = new int[n][2];
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 시작시간, 끝나는 시간순으로 정렬
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) return o1[1] - o2[1];
				return o1[0] - o2[0];
			}
		});
		
		// 맨 첫 강의 끝나는 시간 pq에 넣기
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		pq.add(arr[0][1]);
		
		// 동시에 시작하거나, 더 이후에 시작하는 경우 pq에서 값 빼기
		for (int i = 1; i < arr.length; i++) {
			if (pq.peek() <= arr[i][0]) pq.poll();
			pq.add(arr[i][1]);
		}
		
		System.out.println(pq.size());	
		
	}
}