C++ | faster than 97%
The not so difficult solution is to use a sliding window (2 pointer) approach to find the next location each time a seat is asked. That would take O(n) and ther
The not so difficult solution is to use a sliding window (2 pointer) approach to find the next location each time a seat is asked. That would take O(n) and there is a leetcode for that. First tried and that approach exceeds the time limit for the last test cases. So O(n) for each command is not acceptable.\nThe solution I found to work (instead of tracking which seats are free or taken), was to track the spaces. I have created a set of spaces - spaces are defined by the { distance to next person if someone sits in this space, first empty seat, last empty seat}\nThen the set is ranked by 1- First the descending based on distance to next person and 2- Second ascending based on seat number. set in C++ is created by BST so the ranking takes O(logm) that m is the number of spaces. \nIt is probably possible to make the code look cleaner.\n\nInteresting NOTE: I also tried to pass just the index of first empty and last empty to the set and track only a set of {first empty, last empty} and then rank the set by calculating the distance in the compare function of the struct. But unfortunately, with the version of C++ in leetcode, it seemed that it is not possible to pass down any member to a nested class or struct ... and I had to pass the array size at minimum to calculate the distances\n\n```\nclass ExamRoom {\npublic:\n    \n    int num;\n    ExamRoom(int n) {\n    num = n;\n    spaces.insert({n, 0, n - 1});\n    }\n    \n    int seat() {\n    vector<int> location = *spaces.begin();\n    spaces.erase(spaces.begin());\n    int s = 0;\n    if(location[1] == 0){\n        s = 0;\n        if(location[2] == num - 1)\n            spaces.insert({num-2, 1, num-1});\n        else \n            if(location[2]>=1) spaces.insert({(location[2]-1)/2, 1, location[2]});\n    }\n    else if(location[2] == num - 1){\n        s = num - 1;\n        if(location[1] == 0)\n            spaces.insert({num-1, 0, num - 1});\n        else\n           if(location[1]<=num-2) spaces.insert({(num -2 -location[1])/2, location[1], num - 2}); \n    }\n    else{\n        s = (location[1] + location [2]) / 2;\n        if(s - location[1] > 0) \n            spaces.insert({(s - 1 - location[1])/2, location[1], s- 1});\n        if(location[2] - s > 0) \n            spaces.insert({(location[2] - s - 1)/2, s + 1, location[2]});\n   }\n    return s;\n    }\n    \n    void leave(int p) {\n    set<vector<int>>::iterator before = spaces.end();\n    set<vector<int>>::iterator after = spaces.end();\n    \n    for(auto i = spaces.begin(); i!=spaces.end();i++){\n        if((*i)[1] == p+1)\n            after = i;\n        if((*i)[2] == p-1)\n            before = i;\n        }\n        \n    if(p == 0){\n        vector<int> temp = {0, p, p};\n        if(after!=spaces.end()){\n            temp = *after;\n            spaces.erase(after);}\n        \n        spaces.insert({temp[2], 0, temp[2]});\n    }\n    else if(p == num-1){\n        vector<int> temp {0, p, p};\n        if(before!=spaces.end()){\n            temp = *before;\n            spaces.erase(before);}\n        \n        spaces.insert({num - temp[1]-1, temp[1], num-1});\n    }\n    else{\n        vector<int> temp1 = {0, p, p};\n        if(before!=spaces.end()){\n            temp1 = *before;\n            spaces.erase(before);\n        }\n        \n        vector<int> temp2 = {0, p, p};\n        if(after!=spaces.end()){\n            temp2 = *after;\n            spaces.erase(after);\n        }\n        \n        spaces.insert({(temp2[2]-temp1[1])/2, temp1[1], temp2[2]});\n    }\n     return;  \n    }\n    \nstruct veccompare{\n    bool operator()(vector<int> const & a, vector<int> const & b) const{\n        if(a[0] == b[0])\n            return a[1] < b[1];\n    return a[0] > b[0];\n  }  \n};\n    \nset<vector<int>, veccompare> spaces;\n};\n\n\n```
[]