221 words
1 minutes
[BOJ] 강의실 2
| TimeLimit | MemoryLimit | Condition | TAG |
|---|---|---|---|
| 2s | 128MB | (1 ≤ N ≤ 100,000) | Greedy |
그냥 priority_queue 써서 먼저 채워버리는 방식이면 되는데 티어가 priority_queue 때문에 뻥튀기 됨.
정답 코드
#define MOD 1000000
#define MAX 200000001
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
using ll = long long;
using namespace std;
int n;
struct info {
int number;
int start, finish;
};
vector<int> rooms;
int members[100001];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
auto cmp =[](const info& a, const info& b){
if(a.start > b.start) return true;
else if(a.start == b.start) return a.finish > b.finish;
return false;
};
cin >> n;
priority_queue<info, vector<info>, decltype(cmp)> q;
// 오 이거 신기하네
for(int i = 0; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
info current = {a, b, c};
q.push(current);
}
while(!q.empty()){
info current = q.top(); q.pop();
bool canIn= false;
for(int i = 0; i < rooms.size(); i++){
if(rooms[i]<= current.start){
members[current.number] = i+1;
canIn = true;
rooms[i] = current.finish;
break;
}
}
if(!canIn){
rooms.push_back(current.finish);
members[current.number] = rooms.size();
}
}
cout << rooms.size() <<"\n";
for(int i = 1; i <= n; i++){
cout << members[i] << "\n";
}
return 0;
}
//

