[ boj : 1374,1379 ] 강의실, 강의실2

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

1374번: 강의실

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

1379번: 강의실 2

 

문제 : 각 강의가 시작하는 시간과 끝나는 시간 그리고 강의 번호가 주어집니다. 이때 강의실을 최소로 사용하고 싶어할때 강의실의 개수와 강의번호 순서대로 강의실의 번호를 부여하여 출력하세요

해설 : 일차원 좌표 상에 각 강의가 시작되고 끝나는 시간을 한번 체크해 보세요. 그럼 우린 한가지 규칙을 발견하게 되는데 어떤 한 강의가 끝나기 전까지 다른 강의들이 계속 진행중이라면 새로운 강의실을 할당해줘야 된다는 것입니다.

그렇다면 어떤 한 강의가 끝나는 시점마다 지금까지 진행 중인 강의의 개수를 확인해서 최대값을 갱신해 주면 되겠죠.

#include<bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;

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

	int test;
	cin >> test;
	v.resize(test);
	
	int x;
	for (int i = 0; i < test; i++) {
		cin >> x;
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(), v.end());
	
	int ans = 0;
	priority_queue<int> pq;
	for (int i = 0; i < v.size(); i++) {
		while (!pq.empty() && -pq.top() <= v[i].first)
			pq.pop();
		pq.push(-v[i].second);
		ans = max(ans, (int)pq.size());
	}
	cout << ans;
	return 0;
}

이게 강의실1 입니다.

이제 강의실2를 보면 각 강의들을 임의의 강의실에 할당해주어야 되는데 이를 어떻게 잘 해줘야 될지 생각해 봐야합니다. 결국 관건은 강의실이 끝나는 시점에 지금까지 진행 중인 강의들이 사용되고 있는 강의실들을 잘 분배해 주는 것 입니다. 

전 우선순위 큐 3개를 사용했습니다. 

A : { 시작시간, 강의번호 } , B : { 끝나는 시간, 강의번호 }, C : { 강의번호, 강의실 번호}

그리고 map을 하나 선언해 주어 현재까지 어떤 강의실을 강의들에게 분배해 주었는지 기록을 남겨주었습니다. 이래야지 어떤 강의실이 반환이 되고 새롭게 사용되는지 알 수 있으니까요. 

시작시간<끝나는 시간 인 경우에는 강의실을 하나씩 할당해주면서 A에서 pop 해주었습니다. 동시에 어떤 강의가 몇번 강의실을 사용했는지 map에 기록해주었습니다.

그 외에는 강의에 배정되어 있는 강의실을 반환해주고 어떤 강의에 몇번 강의실을 사용했는지 map에서 찾아와서 강의번호와 강의실 번호를 저장해주었습니다. 

#include <bits/stdc++.h>
using namespace std;

struct info {
	int x, y;
	bool operator<(const info& cur) const {
		return x > cur.x;
	}
};

int n;
priority_queue<info> A, B;
priority_queue<int, vector<int>, greater<int>> C;
map<int, int> mp;
vector<pair<int,int>> ans;

int main() {
	int x, y, z;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z;
		A.push({ y,x });
		B.push({ z,x });
		C.push(i + 1);
	}
	int cnt = 0, ret = 0;
	while (!B.empty())
	{
		if (!A.empty() && A.top().x < B.top().x) {
			mp[A.top().y] = C.top();
			A.pop();
			C.pop();
			ret++;
			cnt = max(cnt, ret);
		}
		else {
			ans.push_back({ B.top().y,mp[B.top().y] });
			C.push(mp[B.top().y]);
			B.pop();
			ret--;
		}
	}
	cout << cnt << "\n";
	sort(ans.begin(), ans.end());
	for (auto u : ans)
		cout << u.second << "\n";
	return 0;
}