G11000. 강의실 배정

문제

제출 코드

• 사용 알고리즘 : 그리디, 자료구조

강의실 정보를 수업 시작시간 기준으로 오름차순 정렬하고, 앞에서부터 사용가능한 강의실이 없으면 강의실을 추가하는 식으로 풀었다.

우선순위 큐에 강의실의 수업이 끝나는 시간들만 저장하여, 가장 수업이 빨리 끝날 강의실을 우선으로 배정해주도록 하였다.

package gold;

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

public class G11000_classroomAssignment {

	static class Class implements Comparable<Class>{
		int start, end;
		Class(int start, int end){
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(Class o) {
			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());

		Class[] classList = new Class[N];
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			classList[i] = new Class(start, end);
		}

		Arrays.sort(classList);

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		queue.add(0);
		int cnt = 1;
		for(int i=0; i<N; i++) {
			if(queue.peek() <= classList[i].start) {
				queue.poll();
			}else {
				cnt++;
			}
			queue.add(classList[i].end);
		}

		System.out.println(cnt);
	}

}