room_allocation.cpp (1197B)
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 using ui = unsigned int; 6 using l = long; 7 using ul = unsigned long; 8 using ll = long long; 9 using ull = unsigned long long; 10 11 using vi = vector<int>; 12 using vui = vector<ui>; 13 using vl = vector<l>; 14 using vul = vector<ul>; 15 using vll = vector<ll>; 16 using vull = vector<ull>; 17 18 void solve() 19 { 20 int n; 21 cin >> n; 22 vector<pair<pair<int, int>, int>> t; 23 vector<int> res(n); 24 for (int i = 0; i < n; i++) { 25 int s, e; 26 cin >> s >> e; 27 t.push_back({{s, 1}, i}); 28 t.push_back({{e + 1, -1}, i}); 29 } 30 sort(t.begin(), t.end(), 31 [](auto &l, auto &r) { 32 if (l.first.first == r.first.first) { 33 return l.first.second < r.first.second; 34 } 35 return l.first.first < r.first.first; 36 }); 37 int cur = 0, m = 0; 38 for (auto x : t) { 39 cur += x.first.second; 40 m = max(m, cur); 41 } 42 cout << m << "\n"; 43 set<int> rooms; 44 for (int i = 0; i < m; i++) { 45 rooms.insert(i+1); 46 } 47 48 for (auto x : t) { 49 if (x.first.second == 1) { 50 res[x.second] = *rooms.begin(); 51 rooms.erase(res[x.second]); 52 } else { 53 rooms.insert(res[x.second]); 54 } 55 } 56 57 for (auto x : res) { 58 cout << x << " "; 59 } 60 cout << "\n"; 61 } 62 63 int main() 64 { 65 ios::sync_with_stdio(0); 66 cin.tie(0); 67 solve(); 68 }