[백준][BOJ-11000][JAVA] 강의실 배정

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

11000번: 강의실 배정

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

public class Main {
	final static int MAX_VALUE = 200001;
	static int[] parents = new int[MAX_VALUE];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		List<Time> list = new ArrayList<>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list.add(new Time(a,b));
		}
		
		Collections.sort(list, (a,b) -> a.start - b.start);
		PriorityQueue<Time> pq = new PriorityQueue<>((a,b) -> a.end - b.end);
		pq.add(list.get(0));
		
		for(int i=1; i<list.size(); i++) {
			Time t = list.get(i);
			if(t.start >= pq.peek().end) {
				pq.poll();
			}
			pq.add(t);
		}
		
		
		System.out.println(pq.size());
	}
}

class Time{
	int start;
	int end;
	public Time(int start, int end) {
		super();
		this.start = start;
		this.end = end;
	}
}

정리

일단 회의실 배정은 시작이 빠른 순서대로 먼저 진행되어야 한다. 따라서 List에 저장되어 있는 값을 시작 시간 오름차순으로 정렬 주었다.

그리고 그에 따라 적게 사용하기 위해선 종료시간과 다음 회의 시작시간 사이의 텀이 아주 적어야 한다.

그래서 시작 시간을 정렬한 list와 종료시간을 비교할 수 있는 우선순위 큐를 선언해준다. 

예시로 한 번 이해해 보도록 하자!

arr[0] = 0 6
arr[1] = 1 4
arr[2] = 2 5
arr[3] = 3 7
arr[4] = 4 8
arr[5] = 5 10

결과부터 말하자면 우선순위 큐의 사이즈가 결국 배정받은 강의실이 된다.

위와 같은 예시에서 먼저 arr[0]번째는 무조건 강의실 배정받아야 하므로 우선순위 큐에 넣어준다. ( 강의실 1 )

그리고 arr[1]의 시작 시간은 1이고 우선순위 큐 맨 위의 종료 시간(가장 빨리 끝나는 강의실 시간)은 6이다. 그러면 아직 회의가 끝난 게 아니므로 강의실을 배정받아야 한다. 따라서 우선순위 큐에 넣어준다. ( 강의실 2 )

arr[2]도 시작시간은 2인데 arr[1]의 값이 들어갔기 때문에 종료시간은 4이다. 근데 아직 회의가 끝난 게 아니므로 강의실 배정을 받아야 한다. ( 강의실 3 ) 따라서 우선순위큐에 넣어준다. arr[3]도 똑같다. ( 강의실 4 )

arr[4]는 시작시간이 4이고 가장 빨리 끝나는 강의실 시간이 4이다. 그러므로 이어서 진행하면 되니깐 강의실을 비워준다 즉! 우선순위 큐에서 제거해준다. 그리고 arr[4]의 값을 넣어준다. ( 강의실이 비워도 그 강의실에 다시 들어가기 때문에 ) ( 강의실 4 )

정리하면 끝에 우선순위 큐의 사이즈가 결국 배정받은 강의실이 된다. 아래의 예시 같은 경우 계속 우선순위 사이즈가 1을 유지 하기에 강의실은 1개만 필요!

arr[0] = 0 1
arr[1] = 1 2
arr[2] = 2 3