问题：
设计类：
给定N个座位。
入座：seat：给当前进入的考生，安排最远距离座位，返回座位号。
离开：leave(p)：座位号为p的考生离开考场，该座位空出来。
Example 1: Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]] Output: [null,0,9,4,2,null,5] Explanation: ExamRoom(10) -> null seat() -> 0, no one is in the room, then the student sits at seat number 0. seat() -> 9, the student sits at the last seat number 9. seat() -> 4, the student sits at the last seat number 4. seat() -> 2, the student sits at the last seat number 2. leave(4) -> null seat() -> 5, the student sits at the last seat number 5. Note: 1 <= n <= 10^9 ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases. Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.
解法：SystemDesign
动态添加元素，选择最大距离位置添加。
这种问题，本来使用已排序功能的数据结构set or map 都比较好。
但由于comparator的构造比较困难，涉及到业务变量N的参照，本次未使用该方法。
思路：
?? 注意：两端的座位，与中间座位的距离判断不同。
逻辑：
代码参考：
1 class ExamRoom { 2 private: 3 int N; 4 vector<int> L; 5 public: 6 ExamRoom(int n) { 7 N=n; 8 } 9 10 int seat() { 11 if(L.empty()) { 12 L.push_back(0); 13 return 0; 14 } 15 int maxdis = max(L[0], N-1-L[L.size()-1]);//get two bound distance. 16 //find maxdis 17 for(int i=1; i<L.size(); i++) maxdis = max(maxdis, (L[i]-L[i-1])/2); 18 19 //insert p at maxdis 20 //test pos:0 21 if(maxdis==L[0]) { 22 L.insert(L.begin(), 0); 23 return 0; 24 } 25 //test middle pos 26 for(int i=1; i<L.size(); i++) { 27 if((L[i]-L[i-1])/2 == maxdis) { 28 L.insert(L.begin()+i, L[i-1]+maxdis); 29 return L[i]; 30 } 31 } 32 //test pos:N-1 33 L.push_back(N-1); 34 return N-1; 35 } 36 37 void leave(int p) { 38 for(int i=0; i<L.size(); i++) { 39 if(L[i] == p) L.erase(L.begin()+i); 40 } 41 } 42 }; 43 44 /** 45 * Your ExamRoom object will be instantiated and called as such: 46 * ExamRoom* obj = new ExamRoom(n); 47 * int param_1 = obj->seat(); 48 * obj->leave(p); 49 */
原文：https://www.cnblogs.com/habibah-chang/p/14855321.html