[BaekJoon] 11000 강의실 배정 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/11000

2.  문제

요약

• $S_i$에 시작해서 $T_i$에 끝나는 N개의 수업이 있는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 합니다.
• 수업이 끝난 직후에 다음 수업을 시작할 수 있습니다.
• N개의 수업에 대한 시작 시간과 끝나는 시간이 주어질 때, 사용할 강의실의 최소 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 200,000보다 작거나 같은 수업의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에는 0보다 크거나 같고 $10^9$보다 작거나 같은 $S_i$와 $T_i$가 주어집니다.
• 출력: 첫 번째 줄에 최소의 강의실 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {
	public int getClassroomNum(Class[] class_list) {
		Arrays.sort(class_list);
		PriorityQueue<Integer> pqueue = new PriorityQueue<>();
		pqueue.offer(class_list[0].end);
		for(int i = 1; i < class_list.length; i++) {
			if(pqueue.peek() <= class_list[i].start) {
				pqueue.poll();
			}
			pqueue.offer(class_list[i].end);
		}
		return pqueue.size();
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		Class[] class_list = new Class[num];
		for(int i = 0; i < num; i++) {
			String[] input = br.readLine().split(" ");
			class_list[i] = new Class(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
		}
		br.close();
		Main m = new Main();
		bw.write(m.getClassroomNum(class_list) + "\n");
		bw.flush();
		bw.close();
	}
	
	public static class Class implements Comparable<Class> {
		int start, end;
		public Class(int start, int end) {
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(Class c) {
			// TODO Auto-generated method stub
			if(this.start < c.start) {
				return -1;
			} else if(this.start > c.start) {
				return 1;
			} else {
				if(this.end < c.end) {
					return -1;
				} else if(this.end > c.end) {
					return 1;
				} else {
					return 0;
				}
			}
		}
	}
}

4.  접근

• 최소의 개수로 강의실을 사용하기 위해서는 강의 사이에 텀을 최대한 줄이며 한 강의실에 많은 강의를 배치해야합니다.
• 그렇게 하기 위해서 주어진 수업들을 시작 시간을 기준으로 오름차순으로 정렬하고 만약 시작 시간이 같다면 종료 시간을 기준으로 오름차순으로 정렬합니다.
• 이와 같이 정렬한 후에 강의실에 수업들을 배치시켜보면 강의 사이에 텀을 최소화 할 수 있음을 알 수 있습니다.
• 필요한 강의실의 최소 개수를 구하기 위해서는 이전 수업의 종료 시간과 배치시키려고 하는 수업의 시작 시간을 비교해야합니다.
• 각 수업은 시작 시간을 기준으로 정렬되어 있기 때문에 이전 수업보다 시작 시간이 느릴 수 없기 때문에 이러한 경우를 배재합니다.
• 이전 수업 시간 사이에 배치하려는 수업의 시작 시간이 위치한다면, 해당 강의실에는 해당 수업을 배치시킬 수 없기 때문에 또 다른 강의실 하나를 사용해야 합니다.
• 이러한 것을 구현하기 위해 PriorityQueue를 이용합니다.
• PriorityQueue에 첫 번째 강의의 종료 시간을 넣고 오름차순으로 정렬하도록 하며 배치하려는 수업들의 시작 시간과 PriorityQueue에서의 가장 빠른 종료 시간을 비교하여 만약 종료 시간보다 늦다면 PriorityQueue에서 가장 빠른 종료 시간을 제거하고 해당 강의의 종료 시간을 PriorityQueue에 넣습니다.
• 이 경우는 PriorityQueue에서 가장 빠른 종료 시간에 해당하는 강의가 이루어지는 강의실에 배치하려는 수업을 배치시킨 것과 같습니다.
• 그렇지 않다면 PriorityQueue에서의 가장 빠른 종료 시간은 제거하지 않고 배정하려는 강의의 종료 시간을 PriorityQueue에 넣습니다.
• 이 경우는 새로운 강의실에 배치하려는 수업을 배치한 것을 의미합니다.

1. 수업의 시작 시간과 종료 시간을 멤버 변수로 가지는 Class 클래스를 생성하고 해당 클래스의 정렬 기준을 시작 시간의 오름차순으로, 시작 시간이 같다면 종료 시간의 오름차순으로 설정합니다.
2. 주어진 수업들의 시작 시간, 종료 시간 정보를 1차원 배열 class_list에 넣고 해당 배열을 Class 클래스의 정렬 기준으로 정렬합니다.
3. 종료 시간들을 넣어놓을 PriorityQueue를 생성하고 class_list의 첫 번째 수업의 종료 시간을 PriorityQueue에 넣습니다.
4. 두 번째 수업부터 마지막 수업까지 반복문을 돌면서 강의실에 각 수업을 배치합니다.
   1. 만약 PriorityQueue에서 가장 빠른 종료 시간보다 현재 배치하려는 수업의 시작 시간이 같거나 느리다면 PriorityQueue에서 가장 빠른 종료 시간을 PriorityQueue에서 제거합니다.
   2. 위 조건과는 상관 없이 PriorityQueue에 현재 배치하려는 수업의 종료 시간을 넣습니다.
5. 4번의 반복문이 끝난 후에 PriorityQueue에 남아있는 종료 시간의 개수가 배치한 강의실의 개수와 같으므로 해당 값을 출력합니다.