855.md

855. Exam Room

Solution 1

class ExamRoom(object):

    def __init__(self, n):
        """
        :type n: int
        """
        from sortedcontainers import SortedList
        self.n = n
        self.s = []

    def seat(self):
        """
        :rtype: int
        """
        if not self.s:
            bisect.insort(self.s, 0)
            return 0
        diff, idx = self.s[0], 0
        for i in range(len(self.s) - 1):
            x = self.s[i]
            y = self.s[i + 1]
            if (y - x) // 2 > diff:
                diff = (y - x) // 2
                idx = x + (y - x) // 2
        if self.n - 1 - self.s[-1] > diff:
            idx = self.n - 1
        bisect.insort(self.s, idx)
        return idx

    def leave(self, p):
        """
        :type p: int
        :rtype: None
        """
        self.s.remove(p)

# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)