[백준] 11000 강의실 배정

문제: 11000번: 강의실 배정

 

#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n; // 수업의 개수
	cin >> n;
	vector<pair<int, int>> times;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;
		pair<int, int> tmp = make_pair(start, end);
		times.push_back(tmp); 
	}
	// 시작 시점을 기준으로 정렬
	sort(times.begin(), times.end());

	// 최소힙으로 동작하도록..
	priority_queue<int, vector<int>, greater<int>> ends;
	ends.push(times[0].second);

	for (int i = 1; i < n; i++) {
		// 끝나는 시간 넣어주기
		ends.push(times[i].second);

		if (ends.top() <= times[i].first) ends.pop();
	}
	// ends 에 남아있는 요소의 수가 강의실의 최소수와 같음
	cout << ends.size() << "\n";

	return 0;
}

 

처음에는 강의를 끝나는 시간을 기준으로 정렬해서 사용하려고 했었다. 반복문을 돌면서 만약 다음 수업 시작 시간이 우선순위큐(최소힙) 에 들어있는 요소보다 작은 경우에(겹치는 수업이 있을 때마다) 회의실 수를 늘리면 되는 건가라는 생각을 했다. 그래서 겹치는 수업이 발생할 때마다 해당 수업의 끝나는 시간을 우선 순위 큐에 넣어 놓은 다음에 다음 시작 시간이 이보다 크거나 같아지면 빼주면 되는 거 아닌가 라고 생각했다.

 

그런데 문제는 지금 끝나는 시간을 기준으로 정렬을 해놨기 때문에 시작 시간이 정렬 안 된 상태로 오는데 이 때문에 다음 시작 시간이 이보다 크거나 같아져서 뺐다고 했을 때 그 다음 수업은 또 반대의 경우가 들어올수도 있어서 안되겠다고 생각했다.

 

그래서 생각해보니까 시작 시간을 기준으로 정렬하면 되는 것이었다... 거의 다 왔는데 결국 다른 블로그의 풀이 로직을 보게 되어서 기분이 좀 안 좋았다. 다음에는 시간이 좀 오래 걸려도 끝까지 풀어봐야 할까라는 고민이 든다. 

 

 

 

참고자료:

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

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