[그리디, 우선순위큐] 백준 1379번 강의실2 C++

※ 문제

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

1379번: 강의실 2

 

※ 풀이

1) [회의실 배정]과 비슷한 문제로, `그리디 알고리즘`을 이용합니다.
다만, `회의실 배정`은 한 장소에서 최대 회의 수를 구하는 문제였다면,
`강의실2`는 모든 장소에서 최대 강의 수를 진행하여 사용하는 최소 강의실 수와 각 강의별 강의실 번호를 구하는 문제입니다.
2) 처음 강의는 `일찍 시작하는 순`으로 오름차순 정렬합니다.
3) `우선순위 큐`를 이용하여 강의 시간이 `일찍 끝나는 순`으로 오름차순 정렬하고, 강의를 하나씩 큐에 넣습니다.
4) 이전에 사용하던 강의실을 사용할 수 있으면 큐에서 제거하고, 사용할 수 없으면 강의실을 새로 추가합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct lecture {
	int num, start, end;
};

struct cmp {
	bool operator()(lecture a, lecture b) {
		return a.end > b.end; // 작은 값 우선
	}
};

bool comp(lecture a, lecture b) {
	return a.start < b.start; // 작은 값 우선
}

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

	int n, ans = 0;
	cin >> n;

	vector<lecture> v(n, { 0,0,0 });
	vector<int> room(n, 0);
	priority_queue<lecture, vector<lecture>, cmp> q;

	for (int i = 0; i < n; i++)	cin >> v[i].num >> v[i].start >> v[i].end;
	sort(v.begin(), v.end(), comp);  // 일찍 시작하는 강의 오름차순

	for (int i = 0; i < n; i++) {
		if (!q.empty() && (q.top().end <= v[i].start))  // 이전에 사용하던 강의실 그대로  {
			room[v[i].num-1] = room[q.top().num - 1];
			q.pop();
		}
		else  // 새로운 강의실 사용 {
			ans++;
			room[v[i].num-1] = ans;
		}
		q.push(v[i]);
	}

	cout << ans << "\n";
	for (int i = 0; i < n; i++) cout << room[i] << "\n";
}