문제

백준 11000 : 강의실 배정

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1 3
2 4
3 5

예제 출력 1

2

문제 풀이

초기 접근

처음에 든 풀이법을은, Ti 만큼의 1차원 배열을 만들어서 강의실을 차지하는 시간을 숫자로 표현할까?였다.
만약 1~3시 수업이라면 1번배열부터 3번배열까지 1로 채운 후, 다음 강의시간이 이전과 겹치면 +1을 해서 2로 채우는 것이다. 그리고 최종적으로, 배열에 들어간 가장 큰 숫자가 필요한 강의실 개수가 된다고 생각했다.

하지만 예상했겠지만 이 풀이의 문제점은...
Si와 Ti의 입력값의 범위가 10^9이라는 것이다. 10^9 크기를 가진 배열을 몇 번 돌면 당연히 시간, 메모리 초과가 발생한다.

풀이 방법

GPT에게 물어보아서 찾은 방법은 우선순위큐를 이용해서 '지금강의'와 '다음에 있을 강의'를 비교해서
지금 강의의 끝나는 시간이 다음에 시작하는 강의의 시작하는 시간보다 작거나 같으면
큐에서 빼고 (새로운 강의실을 추가하지 않고), 그렇지 않으면 큐에 저장(새로운 강의실을 추가)하는 것이다.

이 과정을 거치고 최종적으로 큐의 크기를 구하면 그것이 필요한 강의실의 개수가 되는 것이다.

코드로 보기

1. 강의 시간을 담을 2차원 배열 생성

강의의 시작시간, 끝나는 시간을 담을 2차원 배열을 생성한다.
N개의 강의의 시작, 끝 시작을 담으니 배열의 크기는 아래와 같다.
lecture[N][2]

		//배열 생성하기
		int[][] lectures = new int[N][2];

		for (int i = 0; i < N; i++) {
        	//입력값 받기
			StringTokenizer st = new StringTokenizer(br.readLine());

			int S = Integer.parseInt(st.nextToken());
			int T = Integer.parseInt(st.nextToken());
			//배열에 저장하기
			lectures[i][0] = S;
			lectures[i][1] = T;
		}

2. 배열을 시작 시간이 빠른 순서대로 정렬

'지금 강의'와 '뒤에 있을 강의' 들을 비교하는 것이기 때문에 강의 시간이 빠른 순서대로 정렬해준다.

Arrays.sort(lectures, (a, b) -> a[0] - b[0]);

3. 우선순위 큐 생성, 초기값 삽입

새 강의실이 필요한 수업을 담을 우선순위 큐를 생성하고, 초기값으로 첫번째 수업의 끝나는 시간을 넣는다.

		PriorityQueue<Integer> pq = new PriorityQueue<>();

		pq.offer(lectures[0][1]);

4. 반복문 돌기

반복문을 돌면서 현재 강의의 끝나는 시간과 다음 강의들의 시작 시간을 비교한다.
만약, 현재 강의의 종료시간이 다음 강의들의 시간시간 보다 작거나 같으면
수업이 겹치지 않는다는 의미이기 때문에 새 강의실이 필요하지 않다.
이러한 경우에 큐에서 뺀다.

만약 위의 경우가 아니면 새 강의실이 필요하다는 의미이기 때문에 큐에 남겨둔다.

그리고 다음 강의의 종료시간을 큐에 넣고 반복한다.

		for (int i = 1; i < N; i++ ) {
			//다음 강의의 시작시간과 종료시
			int start = lectures[i][0];
			int end = lectures[i][1];
			
			//현재 강의의 종료시간 <= 다음 강의의 시작
			if (pq.peek() <= start) {
				pq.poll(); //겹치지 않기 때문에 큐에서 빼버
			}
			//다음강의의 종료 시간을 넣
			pq.add(end);
		}

5. 큐의 크기 구하기

4번의 과정에서 새 강의실이 필요한 경우에만 큐에 남겨두었기 때문에, 최종적인 큐의 크기를 구하면 그것이 필요한 강의실의 개수가 된다

		//큐의 크기 구하기  
		System.out.println(pq.size());

회고

우선순위 큐를 잘 활용하자...
간단하게 생각해서, 지금 강의 끝나는 시간 <= 다음 강의 시작 시간을 구하는 로직이라는 것을 기억하자