[BAE/<JOON> 문제풀이] 1379. 강의실2

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

1379번: 강의실 2

 

핵심::

n log n 복잡도로 강의실 사용 추적 

 

풀이::

강의실 문제에서 백트래킹이 추가되었다. 방 개수 세는 로직은 같고

 

stl set으로 사용 가능한 방번호를 계속 추적했다.

 

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

struct cl {
	int cn, s, e;
};

struct room {
	int no, use;
};

struct cmps {
	bool operator()(cl& a, cl& b) {
		if (a.e == b.e) {
			return a.s < b.s;
		}
		return a.e > b.e;
	}
};

priority_queue<cl, vector<cl>, cmps> pq;

bool cmp(cl a, cl b) {
	return a.s < b.s;
}

int main()
{
	int n;
	cin >> n;
	vector<int> arr(n + 1);
	vector<cl> clist(n + 1);
	set<int, less<int>> room;

	for (int i = 1; i <= n; i++) {
		int et;
		int s, e;
		scanf("%d %d %d", &et, &s, &e);
		clist[i] = { et, s, e };
		room.insert(i);
	}

	sort(clist.begin(), clist.end(), cmp);

	arr[clist[1].cn] = 1;
	int mx = -1;
	for (int i = 1; i <= n; i++) {
		int rn = -1;
		while (!pq.empty() && pq.top().e <= clist[i].s) {
			rn = arr[pq.top().cn];
			room.insert(rn);
			pq.pop();
		}
		pq.push(clist[i]);
		int sz = pq.size();
		mx = mx > sz ? mx : sz;
		if (rn == -1) {			
			int fr = *room.begin();
			arr[clist[i].cn] = fr;
			room.erase(fr);
		}
		else {
			arr[clist[i].cn] = rn;
			room.erase(rn);
		}
	}

	cout << mx << "\n";
	for (int i = 1; i <= n; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}