[C++/Java/Python] Straight Forward
Very straight forward idea.\nUse a list L to record the index of seats where people sit.\n\nseat():\n    1. find the biggest distance at the start, at the end a
Very straight forward idea.\nUse a list `L` to record the index of seats where people sit.\n\n`seat()`:\n    1. find the biggest distance at the start, at the end and in the middle.\n    2. insert index of seat\n    3. return index\n\n`leave(p)`: pop out `p`\n\n\n**Time Complexity**:\nO(N) for `seat()` and `leave()`\n\n\n**C++:**\n```\n    int N;\n    vector<int> L;\n    ExamRoom(int n) {\n        N = n;\n    }\n\n    int seat() {\n        if (L.size() == 0) {\n            L.push_back(0);\n            return 0;\n        }\n        int d = max(L[0], N - 1 - L[L.size() - 1]);\n        for (int i = 0; i < L.size() - 1; ++i) d = max(d, (L[i + 1] - L[i]) / 2);\n        if (L[0] == d) {\n            L.insert(L.begin(), 0);\n            return 0;\n        }\n        for (int i = 0; i < L.size() - 1; ++i)\n            if ((L[i + 1] - L[i]) / 2 == d) {\n                L.insert(L.begin() + i + 1, (L[i + 1] + L[i]) / 2);\n                return L[i + 1];\n            }\n        L.push_back(N - 1);\n        return N - 1;\n    }\n\n    void leave(int p) {\n        for (int i = 0; i < L.size(); ++i) if (L[i] == p) L.erase(L.begin() + i);\n    }\n```\n\n**Java:**\n```\n    int N;\n    ArrayList<Integer> L = new ArrayList<>();\n    public ExamRoom(int n) {\n        N = n;\n    }\n\n    public int seat() {\n        if (L.size() == 0) {\n            L.add(0);\n            return 0;\n        }\n        int d = Math.max(L.get(0), N - 1 - L.get(L.size() - 1));\n        for (int i = 0; i < L.size() - 1; ++i) d = Math.max(d, (L.get(i + 1) - L.get(i)) / 2);\n        if (L.get(0) == d) {\n            L.add(0, 0);\n            return 0;\n        }\n        for (int i = 0; i < L.size() - 1; ++i)\n            if ((L.get(i + 1) - L.get(i)) / 2 == d) {\n                L.add(i + 1, (L.get(i + 1) + L.get(i)) / 2);\n                return L.get(i + 1);\n            }\n        L.add(N - 1);\n        return N - 1;\n    }\n\n    public void leave(int p) {\n        for (int i = 0; i < L.size(); ++i) if (L.get(i) == p) L.remove(i);\n    }\n```\n**Python:**\n```\n    def __init__(self, N):\n        self.N, self.L = N, []\n\n    def seat(self):\n        N, L = self.N, self.L\n        if not L: res = 0\n        else:\n            d, res = L[0], 0\n            for a, b in zip(L, L[1:]):\n                if (b - a) / 2 > d:\n                    d, res = (b - a) / 2, (b + a) / 2\n            if N - 1 - L[-1] > d: res = N - 1\n        bisect.insort(L, res)\n        return res\n\n    def leave(self, p):\n        self.L.remove(p)\n```
[]