[BOJ] 백준 11000번 강의실 배정 (Java)

#11000 강의실 배정

난이도 : 골드 5

유형 : 그리디 / 우선순위 큐

11000번: 강의실 배정

▸ 문제

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

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

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

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

▸ 입력

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

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

▸ 출력

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

 

문제 풀이  

1931번 회의실 배정과 유사한 문제이다. 수업의 최대 수는 20만개로 브루트포스로 모든 케이스를 비교하면 시간초과가 발생하게 된다. 그래서 그리디 알고리즘으로 매 최선의 선택을 통해 최적해를 도출해내야 한다.

 

탐욕적인 선택 방법은 '종료시간이 가장 빠른 강의실을 가장 먼저 배정한다.'이다. 이유는 종료되는 강의시간이 빠를수록 후에 더 많은 강의를 배정할 수 있는 확률이 높기 떄문이다.

 

1번 강의 시간 0~4, 2번 강의시간는 0~3이다. 위의 방법이 맞다면 2번 강의실을 먼저 배정해야 한다. 그렇다면 3~8시간에 있는 강의실을 배정할 수 있기 때문에 1번을 고른 경우 4~8시간 보다 선택의 폭이 더 넓어지는 것을 볼 수 있다. 

 

강의실 배정

 

그리고 이러한 방법은 다음 선택에 전혀 영향을 주지 않는다.

• 만약 1번 강의를 골랐다면 이후 선택 가능한 강의는 3번 강의이다.  
• 2번 강의를 선택한 경우엔 3,4,5,6번 강의가 모두 가능하다.

여기까진 두 강의 모두 다음 선택이 가능하니 상관없지만 이후에 1번강의 > 3번강의 이후 선택할 수 있는 강의가 없게 된다. 후자의 경우엔 2번 강의 > 4번 강의 > 6번 강의 총 3개의 강의를 넣을 수 있게 되므로 1~6번 강의를 배치할 때 가능한 최대의 강의 수가 나오게 된다. 이렇게 그리디한 선택 방법이 다음 선택에 영향을 주지 않게 된다.

 

탐욕적 선택 속성 

설계

1. 강의를 시작시간 기준으로 오름차순하고 시작시간이 같을 경우 종료시간을 기준으로 오름차순 한다. Collections.sort(list);
2. 정렬된 강의 데이터를 순차적으로 탐색한다.
   1. 우선순위 큐(최대 힙)에 시작시간이 가장 빠른 강의의 종료시간을 저장한다. q.add(endTime);
   2. 큐에 담겨져있는 강의들 중 가장 빠른 종료시간과 현재 탐색하는 강의의 시작시간이 같거나 더 큰 경우 같은 강의실로 배정한다.
      1. if(!q.isEmpty() && q.peek() <= m.start)
3. 모든 탐색이 끝난 후 현재 남아있는 큐의 사이즈(강의실 배정 개수)를 출력한다. q.size();

 

풀이 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Class implements Comparable<Class>{
		int start;
		int end;
		
		public Class(int start, int end) {
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Class o) {
			if(this.start == o.start) {
				return this.end - o.end;
			}else 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());
		
		StringTokenizer st = null;
		List<Class> list = new ArrayList<>();
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			list.add(new Class(start, end));
		}
		
		Collections.sort(list);
		Queue<Integer> q = new PriorityQueue<>();
		int endTime=0;
		for(Class m : list) {
			endTime = m.end;
			
			if(!q.isEmpty() && q.peek() <= m.start) {
				q.poll();
			}
			q.add(endTime);
		}
		System.out.println(q.size());
	}
}