Best Explanation in whole of solutions 💯 | Don't Miss
Intuition\nThe problem requires us to seat students in such a way that they are seated as far as possible from the already seated students . \nThe challenge lie
# Intuition\nThe problem requires us to seat students in such a way that they are seated as far as possible from the already seated students . \nThe challenge lies in efficiently finding the optimal seat given potentially many occupied seats while ensuring that we can update our data structure when a student leaves. \nThe key observation is that we can treat the empty seats as segments/gaps and determine the best seat to occupy in those segments based on the distance from the occupied seats.\n\n# Approach\n1. **Data Structures**:\n   - **Set**: We use a `set<int>` to maintain a list of occupied seats. This allows us to quickly check which seats are taken and to remove seats efficiently when students leave.\n\n2. **Seating Logic**:\n   - If the room is empty, the first student sits at seat 0.\n   - If there are already occupied seats, we:\n     - Calculate the distance from the start of the row (seat 0) to the first occupied seat.\n     - Check the gaps between each pair of occupied seats to find the maximum distance.\n     - Finally, calculate the distance from the last occupied seat to the end of the row (seat n-1).\n   - The seat that provides the maximum distance from the occupied seats among all empty segments is chosen .\n\n3. **Leaving Logic**:\n   - When a student leaves, we simply remove their seat from the set of occupied seats. \n\n\n# Complexity\n- **Time complexity**: The `seat` operation involves checking each occupied seat, making it $$O(k)$$ where $$k$$ is the number of occupied seats and also it inserts a new ```best_seat``` which takes $$O(logk)$$. Hence the total time complexity of ```seat``` operation is ```O(k+logk)``` \n\n    In worst case ```k``` could go up to ```N``` , so average final time complexity would be $$O(N)$$ ( logN can be ignored )\n\n    The `leave` operation runs in $$O(logN)$$ - since it\'s a ordered set\n\n    \n  \n- **Space complexity**: The space complexity is $$O(k)$$ as we store the occupied seats in a set. This also in worst case can go up to $$O(N)$$\n\n# Code\n```cpp []\nclass ExamRoom {\nprivate:\n    int n;\n    set<int> seats;  // To store occupied seats\n\npublic:\n    ExamRoom(int n) : n(n) {}\n\n    int seat() {\n        if (seats.empty()) {\n            seats.insert(0);\n            return 0;\n        }\n\n        // Calculate the largest gap\n        int max_dist = -1;\n        int best_seat = 0;\n\n        // Check the first seat (0 to first occupied seat)\n        int first = *seats.begin();\n        if (first > 0) {\n            int dist = first; // distance from seat 0 to first\n            if (dist > max_dist) {\n                max_dist = dist;\n                best_seat = 0;\n            }\n        }\n\n        // Check gaps between occupied seats\n        int prev = -1; // previous occupied seat\n        for (int seat : seats) {\n            if (prev != -1) {\n                int dist = (seat - prev) / 2; // distance to the nearest seat\n                if (dist > max_dist) {\n                    max_dist = dist;\n                    best_seat = prev + dist;\n                }\n            }\n            prev = seat;\n        }\n\n        // Check the last seat (last occupied seat to n-1)\n        if (prev != -1 && prev < n - 1) {\n            int dist = n - 1 - prev; // distance from last occupied seat\n            if (dist > max_dist) {\n                best_seat = n - 1;\n            }\n        }\n\n        seats.insert(best_seat);\n        return best_seat;\n    }\n\n    void leave(int p) {\n        seats.erase(p);\n    }\n};\n```\n\n***Upvote if you found it helpful , So it can help many more people ...***\n***And comment if you have any doubts.***\n
['C++']