C++ || Set and Vector
\nstruct interval{\n    static int tot;\n    int l,r;\n    int dist;\n\n    interval(int l,int r){\n        this->l = l;\n        this->r = r;\n        if(l==0)
```\nstruct interval{\n    static int tot;\n    int l,r;\n    int dist;\n\n    interval(int l,int r){\n        this->l = l;\n        this->r = r;\n        if(l==0)dist = r;\n        else if((r+1)==tot)dist = r-l;\n        else dist = (r-l)/2;\n    }\n};\n\nint interval::tot = 0;\nauto comp = [](interval a,interval b)->bool{\n    if(a.dist!=b.dist)\n        return a.dist>b.dist;\n    return a.l<b.l;\n};\n\nset<interval,decltype(comp)> seats(comp);\n\nclass ExamRoom {\npublic:\n    int N = 0;\n    set<int> occupied;\n    ExamRoom(int n) {\n        interval::tot = n;\n        N = n;\n        seats.clear();\n        seats.insert(interval(0,n-1));\n    }\n    \n    int seat() {\n         interval tp = *seats.begin();\n         seats.erase(seats.begin());\n       //  cout<<tp.l<<" "<<tp.r<<" "<<tp.dist<<"||";\n        if(tp.l==0){\n            if(tp.l+1<=tp.r)\n                seats.insert(interval(tp.l+1,tp.r));\n            occupied.insert(tp.l);\n            return tp.l;\n        }else if(tp.r==N-1){\n            if(tp.l<=tp.r-1)\n                seats.insert(interval(tp.l,tp.r-1));\n            occupied.insert(tp.r);\n            return tp.r;\n        }\n        \n        int mid = tp.l+(tp.r-tp.l)/2;\n        \n        if(tp.l<=mid-1)\n            seats.insert(interval(tp.l,mid-1));\n        \n        if(mid+1<=tp.r)\n            seats.insert(interval(mid+1,tp.r));\n        \n        occupied.insert(mid);\n        return mid;\n    }\n    \n    void leave(int p) {\n        auto it = occupied.find(p);\n        // if(it==occupied.begin()){\n        //     cout<<"hello";\n        // }\n        int lperson = it==occupied.begin()?-1:*prev(it,1);\n        int rperson = next(it,1)==occupied.end()?N:*next(it,1);\n\n        seats.erase(interval(lperson+1,p-1));\n        seats.erase(interval(p+1,rperson-1));\n        \n        if((lperson+1)<=(rperson-1))\n            seats.insert(interval(lperson+1,rperson-1));\n        \n        occupied.erase(p);\n    }\n};\n\n/**\n * Your ExamRoom object will be instantiated and called as such:\n * ExamRoom* obj = new ExamRoom(n);\n * int param_1 = obj->seat();\n * obj->leave(p);\n */\n```
['Binary Tree', 'Ordered Set']