C# | Quick learner | Two practices
July 21, 2022\n\nProblem statement:\nThere is an exam room with n seats in a single row labeled from 0 to n - 1.\n\nWhen a student enters the room, they must si
July 21, 2022\n\nProblem statement:\nThere is an exam room with n seats in a single row labeled from 0 to n - 1.\n\nWhen a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0.\n\nDesign a class that simulates the mentioned exam room.\n\nImplement the ExamRoom class:\n\n**ExamRoom(int n)** Initializes the object of the exam room with the number of the seats n.\n**int seat()** Returns the label of the seat at which the next student will set.\n**void leave(int p)** Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.\n\n**Solution 1**: \nUse a C# SortedSet<int> to record the index of seats where people sit.\n\nseat():\n1. Go over each seat and compare to previous seated position, calculate the middle seat; keep the one if the range is maximum distance.\n3. return index\n \n```\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Text;\nusing System.Threading.Tasks;\n\nnamespace _855_exam_room\n{\n    class ExamRoom\n    {\n        static void Main(string[] args)\n        {\n            /*\n            Input\n            ["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]\n            [[10], [], [], [], [], [4], []]\n            Output\n            [null, 0, 9, 4, 2, null, 5]\n            */\n            var examRoom = new ExamRoom(10);\n            var value = examRoom.Seat();  // check return == 0\n            value = examRoom.Seat();  // value == 9\n            value = examRoom.Seat();  // value = 4, 4 and 5 have closest distance 4, but 4 < 5\n            value = examRoom.Seat();  // value = 2 \n            examRoom.Leave(4);\n            value = examRoom.Seat();\n        }\n\n        // study code\n        // https://leetcode.com/problems/exam-room/discuss/1698231/C-SortedSet-solution\n        private SortedSet<int> seats;\n        private int N;\n\n        public ExamRoom(int n)\n        {\n            seats = new SortedSet<int>();\n            N = n;\n        }\n\n        // O(n + logn)\n        public int Seat()\n        {\n            if (seats.Count == 0)\n            {\n                seats.Add(0);\n                return 0;\n            }\n            else\n            {\n                // Seat as far as possible, lowest number as possible, empty then choose 0\n                int maxDistance = seats.First();\n                int prev = -1;\n\n                var seatNumber = 0;\n\n                // sorted seat number - check each range \n                // calculate middle seat \n                // keep the one if it is maximum distance range\n                foreach (var curr in seats)\n                {\n                    // case1 & case 2\n                    int currDistance = prev == -1 ? curr : (curr - prev) / 2;\n\n                    // only keep largest one - \n                    if (currDistance > maxDistance)\n                    {\n                        maxDistance = currDistance;\n                        seatNumber = prev + maxDistance; // prev + maxDistance - lowest as possible!\n                    }\n\n                    prev = curr;\n                }\n\n                // case 3\n                if (N - 1 - prev > maxDistance)\n                {\n                    seatNumber = N - 1;\n                }\n\n                seats.Add(seatNumber);\n                return seatNumber;\n            }\n        }\n\n        // log(n)\n        public void Leave(int p)\n        {\n            seats.Remove(p);\n        }\n    }\n}\n```\n**Solution 2 | Failed one test case**\nJuly 19, 2020\n\nIt is so challenge for me to figure out where the bug is. I have to run visual studio debugger with the failed test case and then figure out. \n\n\n95 / 128 test cases passed.\nStatus: Wrong Answer\nSubmitted: 2 years ago\n\nInput:\n["ExamRoom","seat","seat","seat","leave","leave","seat","seat","seat","seat","seat","seat","seat","seat","seat","leave","leave","seat","seat","leave","seat","leave",\n"seat","leave","seat","leave","seat","leave","leave","seat","seat","leave","leave","seat","seat","leave"]\n[[10],[],[],[],[0],[4],[],[],[],[],[],[],[],[],[],[0],[4],[],[],[7],[],[3],[],[3],[],[9],[],[0],[8],[],[],[0],[8],[],[],[2]]\nOutput:\n[null,0,9,4,null,null,0,4,2,6,1,3,5,7,8,null,null,4,9,null,7,null,3,null,3,null,9,null,null,8,9,null,null,8,9,null]\nExpected: \n[null,0,9,4,null,null,0,4,2,6,1,3,5,7,8,null,null,0,4,null,7,null,3,null,3,null,9,null,null,0,8,null,null,0,8,null]\n\nI will document what I should learn from the failed test case. \n\n```\npublic class ExamRoom {\n    private SortedSet<int>  taken; \n    private int total;\n    public ExamRoom(int N) {\n        if(N <= 0)\n            return;                \n        \n        total = N;\n        taken = new SortedSet<int>();         \n    }\n    \n    public int Seat() {\n        var maximum = 0;\n       \n        var previous = -1; \n        \n        if(taken.Count == 0)\n        {\n            taken.Add(0); \n            return 0; \n        }        \n        \n        var list = taken.ToList(); \n        var max = 0; \n        var number = 0; \n        var range = 0; \n        for(int i = 0; i < list.Count; i++)\n        {            \n            range = i ==0? list[i] : (list[i] - list[i-1]);\n            if(range > max + 1)\n            {\n                max = range;                \n                number = i==0? 0 : (list[i] + list[i-1])/2; \n            }\n        }\n         \n        var lastRange = total - list[list.Count - 1];\n        if(lastRange > max)\n        {\n            max = lastRange;\n            number = total - 1; \n        }\n        \n        taken.Add(number);\n        return number; \n    }\n    \n    public void Leave(int p) {\n        if(p < 0 || p > total - 1)\n            return; \n        \n        taken.Remove(p);            \n    }\n}\n```
[]