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

문제링크 : www.acmicpc.net/problem/11000

11000번: 강의실 배정

익숙한 문제라 정렬 후 그리디로 풀릴 것이라는 것을 짐작하고 풀이에 들어갔다.

 

그래서 정렬된 상태에서 시작시간이 x인 어떤 강의가 강의실이 추가로 필요한 경우는

이전 강의들중에 끝난 강의가 없는 경우이다.

 

끝난 강의를 찾는 방법은 이전 강의를 모두 확인하며 그 개수를 파악하는 방법이 먼저 떠오르겠지만

N이 20만이라 안된다.

 

방법으로는 이전 강의들 중에 가장 빨리 끝나는 강의가 무엇인지 강의 종료 시간을 기준으로 재정렬 => 이분탐색 등을 생각할 수도 있지만 앞으로, 끝난 강의는 재 비교할 필요가 없으므로 우선순위큐를 이용해 top 위치에 가장 빨리 끝나는 강의를 저장하는 방식이 효율적으로 보인다. 

import java.io.*;
import java.util.*;
public class Main {

	public static class Cls {
		int start;
		int end;
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		Cls cls[] = new Cls[N]; 
		for(int i=0;i<N;i++){
			cls[i] = new Cls();
			st = new StringTokenizer(br.readLine());
			cls[i].start = Integer.parseInt(st.nextToken());
			cls[i].end = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(cls,(o1,o2)->o1.start-o2.start);

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		int ans = 0;
		for(int i=0;i<N;i++){
			while(!pq.isEmpty() && pq.peek()<= cls[i].start){
				pq.poll();
			}
			pq.add(cls[i].end);
			ans = Math.max(ans,pq.size());
		}
		System.out.println(ans);
	}

}