#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <list>
#include <cassert>
#include <queue>
using namespace std;

typedef pair<int,int> PII;
typedef vector<pair<int,int>> VII;
typedef vector<vector<pair<int,int>>> VVP;

VVP predavalnice(VII predavanja) {
    VVP urnik;
    sort(predavanja.begin(),predavanja.end());
    for (auto p : predavanja) {
        auto [s,e] = p;
        int x=-1;
        for (int i=0;i<urnik.size();i++) {
            if (urnik[i].back().second<=s) { x=i; break; }
        }
        if (x==-1) urnik.push_back({p});
        else urnik[x].push_back(p);
    }
    return urnik;
}

VVP predavalnice2(VII predavanja) {
    VVP urnik;
    sort(predavanja.begin(),predavanja.end());
    priority_queue<PII, VII, greater<PII>> pq;  // min-heap
    pq.push({predavanja.back().second, -1});
    for (auto p : predavanja) {
        auto [s,e] = p;
        auto [konec, x] = pq.top();
        if (konec<=s) {
            pq.pop(); pq.push({e,x});
            urnik[x].push_back(p);
        } else {
            pq.push({e, urnik.size()});
            urnik.push_back({p});
        }
    }
    return urnik;
}

int main() {
    VII predavanja = {{4,10}, {12,15}, {0,3}, {4,7}, {8,11}, {0,7}, {10,15}, {0,3}, {8,11}, {12,15}};
    VVP urnik = predavalnice2(predavanja);
    for (auto ucilnica : urnik) {
        for (auto [s,e] : ucilnica) printf(" (%d,%d)",s,e);
        printf("\n");
    }
    return 0;
}