room_allocation_1164.cpp (703B)
1 #include <algorithm> 2 #include <iostream> 3 #include <queue> 4 #include <tuple> 5 #include <vector> 6 7 int main() { 8 int n; 9 std::vector<std::tuple<int, int, int>> v; 10 std::cin >> n; 11 for (int i = 0; i < n; i++) { 12 int a, b; 13 std::cin >> a >> b; 14 v.push_back({a, b, i}); 15 } 16 std::sort(v.begin(), v.end()); 17 18 using P = std::pair<int, int>; 19 std::priority_queue<P, std::vector<P>, std::greater<>> r; 20 std::vector<int> al(n); 21 for (auto [a, d, i] : v) { 22 int ind = r.size()+1; 23 if (!r.empty()) { 24 auto [x, j] = r.top(); 25 if (a > x) { 26 r.pop(); 27 ind = j; 28 } 29 } 30 r.push({d, ind}); 31 al[i] = ind; 32 } 33 34 std::cout << r.size() << "\n"; 35 for (auto i : al) 36 std::cout << i << " "; 37 std::cout << "\n"; 38 }