Ravintola

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

typedef long long LL;
using namespace std;

int main(){
    LL n; cin >> n;
    vector<pair<pair<LL,LL>, LL> > v; // start, end, group id
    for(int i = 0; i < n; i++){
        LL x,y; cin >> x >> y;
        v.push_back({{x,y},i});
    }
    sort(v.begin(), v.end());
    multiset<pair<LL,LL> > is_freed; // time, table id
    set<LL> tables;
    LL next_table = 1;
    vector<pair<LL,LL > > ans; // group id, table
    for(auto interval : v){
        LL start = interval.first.first;
        LL end = interval.first.second;
        LL group_id = interval.second;
        while(!is_freed.empty() && is_freed.begin()->first <= start){
            tables.insert(is_freed.begin()->second);
            is_freed.erase(is_freed.begin());
        }
        LL table;
        if(tables.size() != 0){
            table = *tables.begin();
            tables.erase(tables.begin());
        }
        else{
            table = next_table;
            next_table++;
        }
        is_freed.insert({end, table});
        ans.push_back({group_id, table});
    }
    sort(ans.begin(), ans.end());
    cout << next_table - 1 << "\n";
    for(auto x : ans) cout << x.second << "\n";
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED