Swift linear solution
Code\n\n\nclass ExamRoom {\n    // seated is an array of seats taken\n    // a sorted set may be faster\n    var seated: [Int]\n    let n: Int\n\n    init(_ n: 
# Code\n```\n\nclass ExamRoom {\n    // seated is an array of seats taken\n    // a sorted set may be faster\n    var seated: [Int]\n    let n: Int\n\n    init(_ n: Int) {\n        self.n = n\n        seated = []\n    }\n    \n    func seat() -> Int {\n        if seated.isEmpty {\n            seated.append(0)\n            return 0\n        }\n\n        var idx = 0\n        var value = 0\n        var maxDistance = seated[0] // inital distance is first seat to the beginning\n\n        // for each seat that is taken,\n        // calculate the distance between seats\n        for i in 0..<seated.count - 1 {\n            let midDistance = (seated[i + 1] - seated[i]) / 2\n\n            if midDistance > maxDistance {\n                idx = i + 1\n                value = seated[i] + midDistance\n                maxDistance = midDistance\n            }\n        }\n\n        if n - 1 - seated.last! > maxDistance {\n            // distance from last seat taken to the end\n            // is greater than max distance\n            seated.append(n - 1)\n            return n - 1\n        } else {\n            // insert at idx so that the seated array remains sorted\n            seated.insert(value, at: idx)\n            return value\n        }\n    }\n    \n    func leave(_ p: Int) {\n        // remove seat from array\n        seated = seated.filter { $0 != p }\n    }\n}\n\n```
['Swift']