[BOJ] 11000 강의실 배정

11000 강의실 배정

난이도 : 골드5
유형 : 그리디

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

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

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

풀이

최소의 강의실을 사용해서 모든 수업을 가능하게 해야된다는 점에서 정렬을 먼저 떠올렸다.
시작되는 순으로 오름차순으로 정렬해서 최대한 수업시간이 짧은 수업들을 많이 우겨넣어야 최소의 강의실로 운영할 수 있기 때문이다.
끝나는 시간을 계속 우선순위 큐에 넣고, 바로 뒤의 강의시간과 비교하여 끝나는시간이 뒤의 강의시작시간보다 작거나 같으면 큐에서 빼주는 형식으로 풀었다.

코드

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

/**
 * BOJ_11000_G5_강의실 배정
 * @author mingggkeee
 * 그리디 알고리즘
 */
public class BOJ_11000 {
	
	static int N;	// 수업의 개수
	static int [][] arr;	// 수업 시간 저장
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][2];
		for(int i=0; i<N; i++) {
			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[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o1[0]) {
					return o1[1] - o2[1];
				}
				return o1[0] - o2[0];
			}
		});
		
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		queue.add(arr[0][1]);
		
		for(int i=1; i<N; i++) {
			if(queue.peek() <= arr[i][0]) {
				queue.poll();
			}
			
			queue.add(arr[i][1]);
		}
		
		System.out.println(queue.size());
		br.close();
	}
}