Seat Arrivals at the Farthest Available Position

### Problem Implement ExamRoom(n) for seats 0 through n-1. seat() occupies and returns an empty seat maximizing its distance to the nearest occupied seat; break ties by the lowest label. An empty room chooses 0. leave(p) frees an occupied seat. **Operation precondition:** Call seat() only when a free seat exists. ```cpp class ExamRoom { public: ExamRoom(int n); int seat(); void leave(int p); }; ``` ### Examples **Example 1:** ```text ExamRoom(5); seat(); seat(); seat(); seat(); leave(2); seat() Seat returns: [0,4,2,1,2] Explanation: The first midpoint is2; equal-distance choices later favor the smaller label. ``` **Example 2:** ```text ExamRoom(1); seat(); leave(0); seat() Seat returns: [0,0] Explanation: Each arrival has the only seat available. ``` ### Constraints - Seat count n lies in [1,1000000000]. - There are at most 10000 combined seat and leave calls. - A leave(p) call always names an occupied seat. - Every seat() call has at least one free seat. ### Contract considerations Keep the original constructor, seat and leave methods and the smallest-label tie rule. ```hint Read the boundary condition Which positions are the best candidates inside each empty gap? ``` ### Boundary reminders Keep the original constructor, seat and leave methods and the smallest-label tie rule.