[백준] 11000번 강의실 배정 | C/C++

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

3
1 3
2 4
3 5

예제 출력

2

 

풀이

이 문제는 [백준] 1931 회의실 배정 문제와 비슷하다.

다만 회의실 배정 문제와 다른점이 강의실의 개수를 최소로 여러개 사용 가능하다는 점이다.

? priority_queue

우선순위 큐

1. 시작 시간 기준으로 오름차순 정렬을 해준다.
2. 우선순위 큐에 첫번째 수업이 끝나는 시간을(3) Push 한다.
3. 다음 수업의 끝나는 시간(4)를 Push 한다.
4. ! if ! 두번째 수업의 시작 시간(2)이 첫번재 수업의 끝나는 시간(3) 보다 작기에 강의 시간이 겹치므로 강의실이 하나 더 필요하다.
5. 우선순위 큐 상태를 변경하지 않고 두번째 수업의 끝나는 시간(4)를 Push 한다.
6. ! else ! 첫번째 수업의 끝나는 시간(3)보다 세번째 수업의 시작시간(3)이 크거나 같기에, 동시 수강이 가능하다. 따라서 강의실이 추가로 필요하지 않다.
7. 첫번째 수업의 끝나는 시간(3)을 Pop 한다.
8. 마지막으로 3번째 수업의 끝나는 시간(5)를 Push 한다.

 

여기까지하고 실행했는데 오류가 나서 우선순위 큐 클래스를 살펴보았더니 오름차순 정렬을 안 해서 오류 발생!!!!!

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>

• Type : 저장되는 요소 데이터 형식
• Container : 구현하는데 사용되는 기본 컨테이너의 형식
• Compare : 두 요소 값을 정렬 키로 비교하여 상대적 순서를 결정. 이 인수는 선택 사항이며 기본값은 이진 조건자 less<typename Container::value_type>

우선순위 클래스 구문을 살펴 보면 Compare 매개변수의 기본값이 less로 되어 있어서 i수업 종료시간과 i+1수업 시작 시간의 대소 비교가 틀리는 것이었다....!

우선순위 큐를 오름차순 하는 것을 까먹다니!!!!!!!!! 꼮꼮꼭!!!!!!!!!! Compare 매개변수를 greater로 넣어서 정렬 후 사용하시오...

구문의 매개 변수를 잘 확인하자...! 

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int main(void)
{
	int N = 0;
	int begin = 0;
	int end = 0;
	int classcount = 0;
	vector<pair<int, int>> v_time;
	priority_queue<int, vector<int>, greater<int>> pq;

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> begin >> end;
		v_time.push_back(make_pair(begin, end));
	}
	sort(v_time.begin(), v_time.end());

	pq.push(v_time[0].second); //큐에 첫번째 수업 끝나는 시간 추가

	for (int i = 1; i < N; i++)
	{
		//두번째 수업 시작시간이 첫번째 수업 끝나는 시간보다 작을 때 -> 강의 시간이 겹칠 때
		if (pq.top() > v_time[i].first)
		{
			pq.push(v_time[i].second);
		}
		else 
		{
			pq.pop();
			pq.push(v_time[i].second);
		}
	}
	cout << pq.size();
	return 0;
}

---

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

11000번: 강의실 배정