(22.06.25) (Baekjoon) 11000.강의실 배정

11000번: 강의실 배정

시간 제한 : 1초

메모리 제한 : 256MB

 

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

3
1 3
2 4
3 5

예제 출력 1 복사

2

앞서 작성했던 1931.회의실 배정의 응용 버전 문제다.

1931번: 회의실 배정

 

회의실 배정에선 가장 많은 회의를 할 수 있는 시간 분배를 찾아야 했다면,

강의실 배정에선 주어진 강의 시간을 맞추기 위해 필요한 강의실의 수를 출력해야 하는 문제다.

 

강의의 개수가 200,000만개까지 갈 수 있으므로, 완탐은 불가능하다.

우선 정렬은 회의실 배정에서 했던 것처럼 해준다.

Arrays.sort(ar,(o1,o2) -> o1[0] == o2[0] ? o1[1]-o2[1] : o1[0]-o2[0]);

이번 문제에선 람다를 사용하여 정렬해봤다(이렇게도 되더라.. 신기했다.)

시작시간이 같다면 종료시간 오름차순으로, 다르다면 시작시간 오름차순으로 정렬을 진행했다.

 

여기까진 좋은데, 강의실이 몇개가 필요한지 어떻게 알 수 있을까?

일단, 강의 시간의 가장 빠른 원소를 가져와보자.(ar[0])

해당 강의가 끝나기 전에 다른 강의가 있으면 -> 다른 강의실이 더 필요함

해당 강의가 끝난 후에 다른 강의가 있으면 -> 다른 강의실이 없어도 됨

 

강의 시간을 저장한 배열은 정렬을 끝내놓은 상황이다. 그렇다면 현재 가장 빠른 종료시간을 기억하고 다음 시작시간과 비교하면 해결될 수 있는 일이다!

이 부분에서 "우선순위 큐"가 사용된다.

pq.offer(ar[0][1]); // 정렬 후 0번째 강의의 종료시간을 저장
		
		for (int i = 1; i < n; i++) { // 첫번째~n-1번째 강의를 하나씩 둘러보자.
			if(pq.peek() <= ar[i][0]) { 
            // 현재 우선순위큐(최소힙)의 루트값보다 i번째 강의의 시작시간이 더 크다면
            // => 강의실이 늘어날 필요가 없음(ex. 1 3 <= 5 6)
				pq.poll();
			}
            // 만약 위 조건이 만족하지 못한다면(ex. 1 3 > 2 4)
            // 최소 시간은 그대로 유지
			pq.offer(ar[i][1]);
            // 시간이 갱신되거나 새로운 강의를 찾았을 경우 그 값을 pq에 삽입 => 시간 갱신될 수 있음
		}

위 코드를 통해 강의실의 최대 갯수를 구할 수 있으며, pq의 최종 크기를 구하면 정답이다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[][] ar = new int[n][2];
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			ar[i][0] = Integer.parseInt(st.nextToken());
			ar[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(ar,(o1,o2) -> o1[0] == o2[0] ? o1[1]-o2[1] : o1[0]-o2[0]);
		// 시간 순 정렬 완료("회의실 배정" 문제 참고)
		// 완탐 : for문을 돌려 시간이 되는 강의들을 모두 방문 처리해주고, 모든 강의를 들을 때까지 전 과정을 반복해줌.(200000 * 200000)(O(n^2)) ==> 억이 넘어갈 수 있으므로 불가능.
		/*
		 강의들별로 그룹을 지정해줌.
		 ex. 1 3 // 2 4 // 3 5 ==> 1 3과 3 5는 1그룹 // 2 4는 2그룹
		 그룹 수를 출력해주면 끝.
		 
		 그렇다면 그룹을 어떻게 잡아줘야 할까?
		 완탐은 X.
		 
		 */
//		
//		for (int i = 0; i < n; i++) {
//			System.out.println(ar[i][0] + " " + ar[i][1]);
//		}
		int cnt = 0;
		pq.offer(ar[0][1]);
		
		for (int i = 1; i < n; i++) {
			if(pq.peek() <= ar[i][0]) {
				pq.poll();
			}
			pq.offer(ar[i][1]);
		}
		
		System.out.println(pq.size());
	}
}