강의실 배정 (백준)

처음 내가 접근했던 방법은 다음과 같다.

 

1. 수업 시작 시간을 기준으로 오름차순하여 정렬한다.

2. 강의실을 담을 벡터 컨테이너를 선언한다. (벡터에 들어가는 값은 수업이 끝나는 시간이다.)

3. 첫 번째 수업이 끝나는 시간을 벡터에 담는다. 이때 강의실은 1개이다.

4. 벡터에서 강의실 수업이 끝나는 시간이 두 번째 수업 시작시간 보다 크거나 같은 경우 해당 강의실의 수업 종료 시간을 두 번째 수업 종료 시간으로 갱신한다.

5. 만약 벡터에서 만족하는 강의실을 찾지 못한 경우, 강의실을 추가하고 해당 수업 종료 시간을 값으로 넣는다.

6. 4 ~ 5 작업을 마지막 수업까지 반복한다.

7. 벡터의 사이즈를 출력한다

코드는 다음과 같다.

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

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(2));
	for (int i = 0; i < n; ++i)
		cin >> v[i][0] >> v[i][1];	

	sort(v.begin(), v.end()); // 오름차순 정렬
	vector<int> info(1, v[0][1]); // 강의실을 담을 컨테이너, 첫 번째 강의실 종료 시간을 담음

	// 두번째 강의실 부터 마지막 강의실까지
	for (int i = 1; i < v.size(); ++i)
	{
		bool check = false;
		// 이용 가능한 강의실이 있는지 찾는다.
		for(auto& iter : info)
		{
			// 이용 가능한 강의실이 있는 경우 해당 수업 종료 시간으로 갱신한다.
			if (iter <= v[i][0])
			{
				iter = v[i][1];
				check = true;
				break;
			}
		}
		if (check) continue;
		// 만족하는 강의실이 없는 경우 강의실을 추가한다.
		info.push_back(v[i][1]);
	}

	cout << info.size() << endl;
}

하지만 이 방법은 수업마다 매번 가지고 있는 강의실을 살펴봐야 하기 때문에 시간초과가 난다.

 

그렇기 때문에 이 방법은 사용이 불가능하다.

 

시간초과를 해결하는 방법은 바로 힙을 사용하는 것이다. 최소 힙을 사용하여 수업의 종료 시간을 담아놓는다. 그리고 수업이 먼저 끝나는 강의실에서 수업 종료 시간이 다음 수업 시작 시간보다 작거나 같은 경우 해당 강의실에서 다음 수업을 진행하면 된다. 만약 만족하지 않는 경우에는 힙에 강의실을 추가하면 된다.

 

코드는 다음과 같다.

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

int main()
{
	int n;
	cin >> n;
	vector<vector<int>> v(n, vector<int>(2));
	for (int i = 0; i < n; ++i)
		cin >> v[i][0] >> v[i][1];	

	sort(v.begin(), v.end()); // 오름차순 정렬
	priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙 선언
	pq.push(v[0][1]); // 강의실에 첫 번째 수업 종료 시간을 담는다. 
	for (int i = 1; i < v.size(); ++i)
	{
        // 강의실 조건을 만족하는 경우 강의실 삭제(어차피 뒤에서 강의실을 추가하므로)
		if (v[i][0] >= pq.top()) pq.pop();
        // 해당 수업을 위한 강의실을 추가한다.
		pq.push(v[i][1]);
	}
	cout << pq.size() << endl;
}