백준 11000 강의실 배정 (Java)

1. 문제 링크

11000번: 강의실 배정

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 우선순위 큐를 이용해서 시작 시간 기준 정렬하고, 시작이 같은 경우에는 종료 기준으로 정렬했다.

2. 강의실에 배정 받은 수업을 통과 큐에 넣고 큐 안의 수업과 비교했다.

3. 통과 큐에 아무것도 없거나, 통과 큐 안의 것보다 시작 시간이 앞이라면 통과큐에 넣는다. (새로운 강의실)

4. 통과 큐 안의 것보다 시작 시간이 크거나 같은 경우에는 통과 큐 안의 것과 바꿔치기한다. (비교 대상을 지금 수업으로 바꿈)

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	static class Class implements Comparable<Class>{
		int start;
		int end;
		public Class(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(Class o) {
			if(this.start == o.start) {
				return this.end - o.end;
			}
			return this.start - o.start;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Class> pq = new PriorityQueue<>();
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			int a = Integer.parseInt(split[0]);
			int b = Integer.parseInt(split[1]);
			pq.offer(new Class(a, b));
		}
        
		PriorityQueue<Integer> pass = new PriorityQueue<>();
		while(!pq.isEmpty()) {
			Class now = pq.poll();
            
      		//통과한 녀석의 끝나는 시간이랑 비교해서 가능한 시간이라면
			if(!pass.isEmpty() && now.start >= pass.peek()) { 
				pass.poll(); 
			}
			pass.offer(now.end);
		}
		System.out.println(pass.size());
	}
}