[BOJ-11000][우선순위 큐] 강의실 배정 - Java

문제 바로가기

11000번: 강의실 배정

 

문제 이해하는데 한참 걸렸네;;

한 번 사용한 강의실을 재 사용할 수 있는지 체크하면 됩니다.

 

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

public class Main {
	static class Lec implements Comparable<Lec> {
		int s, t;
		Lec(int s, int t){
			this.s = s; this.t = t;
		}
		
		public int compareTo(Lec o) {
			return this.t - o.t;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Lec> pq = new PriorityQueue<>();
		List<Lec> lectures = new ArrayList<>();

		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			lectures.add(new Lec(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}

		Collections.sort(lectures, new Comparator<Lec>() {
			public int compare(Lec o1, Lec o2) {
				if(o1.s == o2.s) return o1.t - o2.t;
				return o1.s - o2.s;
			}
		});
		
		for(Lec l : lectures) {
			if(pq.isEmpty()) pq.offer(l);
			else {
				if(pq.peek().t <= l.s) {
					pq.poll();
					pq.offer(l);
				}else pq.offer(l);
			}
		}
		System.out.println(pq.size());
	}
}

먼저 강의를 시작 시간 오름차순으로 정렬합니다.

왜냐면 강의가 끝나는 대로 찹찹 넣을 것이기 때문이죠.

 

그리고 종료 시간으로 우선 순위 큐를 만들어 줍니다.

pq.peek().t <= l.s 라면 썼던 강의실을 그대로 사용할 수 있는 겁니다. 강의가 끝나고 나서 그 강의실에서 시작하면 되기 때문이죠.

 

그럴 수 없다면 얌전히 pq에 넣어주기만 합니다.

 

이렇게 반복하면 최종적으로 pq의 사이즈가 바로 사용한 강의실의 개수가 되는 것이죠.

 

 

풀고보니 아주 간단합니다!! 감사합니다!!!!! )?(