각 사람의 컴퓨터 이용 시간과 종료 시간이 주어질 때
사람들이 기다리지 않고 이용할 수 있는 컴퓨터의 최소 개수와 각 자리를 사용한 인원수를 출력하는 문제입니다.
각 사람들의 이용 시간과 종료 시간이 겹치지 않으므로 사람들이 컴퓨터를 사용하는 시간대로 구현해 주시면 됩니다.
시작 시간이 빠른 사람부터 컴퓨터 자리에 앉으면서 비어있는 컴퓨터 자리를 찾아 앉으면 됩니다.
근데 비어 있는 컴퓨터 자리를 찾을 때 O(N^2)으로 찾게 되면 N이 최대 10만이므로 시간 초과가 나게 됩니다.
비어있는 컴퓨터 자리 중 가장 작은 번호 자리에 앉아야 하므로 저는 우선순위 큐를 사용하여 비어있는 자리 번호의 최소 번호를 저장했습니다.
우선 사람들도 시작 시간이 빠른 사람부터 먼저 자리에 앉아야 합니다.
그래서 시작 시간으로 정렬을 해주고 종료 시간이 된 사람들도 자리에서 나와야 하기 때문에 종료 시간이 빠른 순서로 저장해 줘야 합니다.
그래서 종료 시간에 대한 우선순위 큐를 선언하였습니다.
어떤 사람이 이제 컴퓨터를 사용하려는 데 종료 시간 우선순위 큐에 시작 시간보다 빠른 값이 있으면 자리에서 나와야 하므로 나온 사람들의 자리 번호를 비어있는 자리 번호에 추가하였습니다.
그리고 시작 시간 전에 나올 사람들은 다 나왔으니 비어있는 자리 중에 가장 작은 번호에 앉으면 됩니다.
만약 비어있는 자리가 존재하지 않는다면 컴퓨터의 개수를 하나 더 늘리고 그 자리에 앉으면 됩니다.
이렇게 사람들의 시작 시간과 종료 시간을 이용하여 사람들이 앉은 자리 번호를 다 구하시고 필요한 컴퓨터의 개수와 각 자리를 이용한 인원수를 저장하여 출력해 주시면 됩니다.
말 그대로 구현하면 되는 문제라 우선순위 큐를 이용하여 시작 시간, 종료 시간, 비어있는 자리 번호를 잘 관리해 주시면 어렵지 않게 구현하실 수 있습니다!!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define fs first
#define sd second
#define ep emplace
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
using namespace std;
int main() {
FIO;
int n; cin >> n;
vector<pii> v(n);
vector <int> ans;
FOR(i, 0, n - 1) cin >> v[i].fs >> v[i].sd;
sort(all(v));
priority_queue <int> com;
priority_queue <pii> end;
FOR(i,0,n-1){
while(end.size() && v[i].fs >= -end.top().fs) {
com.ep(-end.top().sd);
end.pop();
}
int idx;
if(com.empty()) {
idx = (int)ans.size();
ans.eb(1);
}
else {
ans[idx = -com.top()]++;
com.pop();
}
end.ep(-v[i].sd, idx);
}
cout << (int)ans.size() << '\n';
for(int i : ans) cout << i << ' ';
return 0;
}