백준 11000 - 강의실 배정 ( JAVA )

출처 - 백준 알고리즘

11000번: 강의실 배정

---

[ 알고리즘 ] 

( 우선순위 큐 + 그리디 알고리즘 )

: 최소의 강의실을 사용하기 위해서 , 강의를 시작시간을 기준으로 오름차순 정렬한다. 

 

 

1. 주어진 강의를 int[][] 배열에 시작시간-종료시간으로 저장한다. 

   ( * 시작시간을 기준으로 오름차순 정렬, 만약 시작시간이 같을 경우엔 종료시간 기준 오름차순 ) 

 

2.  우선순위큐에 첫번째 강의의 종료시간을 add 한다. 

 

3.  모든 강의가 끝날 때까지 다음 과정을 반복한다. 

•  큐의 제일 처음원소를 peek() 한다. ( = 현재 사용하고 있는 강의실 중, 가장 빨리 끝나는 강의의 종료시간 ) 
•  현재 강의의 시작시간과 해당 값을 비교한다. 
•  같은 강의실에서 수업할 수 있다면, 해당값을 poll() 하고 강의 종료시간을 갱신하여 add() 한다. 
•  같은 강의실에서 수업할 수 없다면, 현재강의의 종료시간을 add() 한다. 

     ( * 우선순위큐이기 때문에, 제일 앞 원소의 다음 값들은 더 큰 값이므로 고려할 필요 x ) 

 

4. 모든 강의가 끝났을 때 우선순위큐의 size 가 곧 강의실에 갯수이다. 

 

 

 [ 예로, ] 

주어진 예제를 사용해보자. 

1   3 

2   4 

3   5 

일때, 

 

- 큐에 첫번째 강의의 종료시간을 add 

3

- que.peek() = 3 

- 다음 강의 시작시간이 2이므로 , 같은 강의실에서 수업할 수 없다. > 종료시간을 add () 

3

4

- que.peek() = 3 

- 다음 강의 시작시간 3이므로, 같은 강의실에서 수업할 수 있다. > que.poll() , 종료시간 add () 

 ( = 즉, A 강의실에서 강의가 1-3 으로 3에 끝났는데, 1-3-3-5이므로 종료시간을 5로 갱신하는 과정 ) 

4

5

- 결론적으로, 2개의 강의실이 필요 

ex) A 강의실 : 1-3-3-5 

      B 강의실 : 2-4

 

 

 

 + 왜 시작시간 기준일까 ? 

 : 종료시간을 기준으로 했을때의,  반례가 존재한다.

 

ex )  종료시간 기준으로 정렬했을 경우 , 

1   3 

2   4

4   6 

3   8 

 

- 큐에 첫번째 강의의 종료시간을 add 

3

- que.peek() = 3

- 다음 강의 시작시간이 2이므로 , 같은 강의실에서 수업할 수 없다. > 종료시간을 add () 

3

4

- que.peek() = 3

- 다음 강의 시작시간이 4이므로, 같은 강의실에서 수업할 수 없다. > 종료시간 add() 

3

4

6

- que.peek() = 3

- 다음 강의 시작시간이 3이므로, 같은 강의실에서 수업할 수 있다. > que.poll() , 종료시간 add () 

4

6

8

- 결론적으로, 3개의 강의실이 필요

ex) A 강의실 : 1-3-3-8 

      B 강의실 : 2-4

      C 강의실 : 4-6

 

BUT,  시작시간을 기준으로 하면, 두개의 강의실만 필요함. 

( 1-3, 3-8 ) 

( 2-4, 4-6 ) 

 

---

[ 코드 ]

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
	
		int n = Integer.parseInt(br.readLine());
		int[][] classes = new int[n][2]; // [시작시간][종료시간]
		
		for(int i =0; i<n; i++){
			String s = br.readLine();
			StringTokenizer st= new StringTokenizer(s, " ");
			
			classes[i][0] = Integer.parseInt(st.nextToken()); 
			classes[i][1] = Integer.parseInt(st.nextToken()); 
			
		}
		
		// 시작시간을 오름차순으로 정렬 ( 시작시간이 같다면 종료시간 오름차순 ) 
		Arrays.sort(classes, (s1,s2)->{
			if(s1[0]==s2[0]) return s1[1]-s2[1]; 
			return s1[0]-s2[0]; 
		});
		
		
		PriorityQueue<Integer> lectroom = new PriorityQueue<>();
		for(int i=0; i<n; i++) {
			int start= classes[i][0];
			int end = classes[i][1]; 
			
			// 제일 처음강의 > 종료시간 넣기 
			if(lectroom.isEmpty()) lectroom.add(end); 
			
			else {
				int beforeend = lectroom.peek();
				
				// 같은 강의실에서 들을 수 있는 경우, 
				if(start >= beforeend) {
					// 해당 강의실에 강의 종료시간을 갱신 
					lectroom.poll();
					lectroom.add(end); 
				}
				// 같은 강의실에서 들을 수 없는 경우, 
				else { 
					//우선순위큐이기 때문에, 앞의 강의에 이어지지 않는다면, 다음거도x 
					lectroom.add(end);
				}
			}
		}
	
		System.out.println(lectroom.size());
	}
}