855 Exam Room 考場(chǎng)就座

Description:
There is an exam room with n seats in a single row labeled from 0 to n - 1.

When 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.

Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
int seat() Returns the label of the seat at which the next student will set.
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.

Example:

Example 1:

Input
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
Output
[null, 0, 9, 4, 2, null, 5]

Explanation

ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0.
examRoom.seat(); // return 9, the student sits at the last seat number 9.
examRoom.seat(); // return 4, the student sits at the last seat number 4.
examRoom.seat(); // return 2, the student sits at the last seat number 2.
examRoom.leave(4);
examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints:

1 <= n <= 10^9
It is guaranteed that there is a student sitting at seat p.
At most 10^4 calls will be made to seat and leave.

題目描述:
在考場(chǎng)里，一排有 N 個(gè)座位，分別編號(hào)為 0, 1, 2, ..., N-1 。

當(dāng)學(xué)生進(jìn)入考場(chǎng)后，他必須坐在能夠使他與離他最近的人之間的距離達(dá)到最大化的座位上。如果有多個(gè)這樣的座位，他會(huì)坐在編號(hào)最小的座位上。(另外，如果考場(chǎng)里沒(méi)有人，那么學(xué)生就坐在 0 號(hào)座位上。)

返回 ExamRoom(int N) 類，它有兩個(gè)公開的函數(shù)：其中，函數(shù) ExamRoom.seat() 會(huì)返回一個(gè) int （整型數(shù)據(jù)），代表學(xué)生坐的位置；函數(shù) ExamRoom.leave(int p) 代表坐在座位 p 上的學(xué)生現(xiàn)在離開了考場(chǎng)。每次調(diào)用 ExamRoom.leave(p) 時(shí)都保證有學(xué)生坐在座位 p 上。

示例 :

輸入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
輸出：[null,0,9,4,2,null,5]
解釋：
ExamRoom(10) -> null
seat() -> 0，沒(méi)有人在考場(chǎng)里，那么學(xué)生坐在 0 號(hào)座位上。
seat() -> 9，學(xué)生最后坐在 9 號(hào)座位上。
seat() -> 4，學(xué)生最后坐在 4 號(hào)座位上。
seat() -> 2，學(xué)生最后坐在 2 號(hào)座位上。
leave(4) -> null
seat() -> 5，學(xué)生最后坐在 5 號(hào)座位上。

提示:

1 <= N <= 10^9
在所有的測(cè)試樣例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被調(diào)用 10^4 次。
保證在調(diào)用 ExamRoom.leave(p) 時(shí)有學(xué)生正坐在座位 p 上。

思路:

有序列表
使用 set(C++), TreeSet(Java), sortedcontainers.SortedList(Python) 記錄已經(jīng)坐上去的學(xué)生
當(dāng)記錄為空時(shí), 插入 0 并返回
否則, 遍歷有序列表中的元素, 查找中點(diǎn)與區(qū)間端點(diǎn)距離的最大值并插入有序列表
時(shí)間復(fù)雜度為 O(nlgn), 空間復(fù)雜度為 O(n)

代碼:
C++:

class ExamRoom 
{
private:
    set<int> seats;
    int size;
public:
    ExamRoom(int n)
    {
        size = n;
    }
    
    int seat() 
    {
        if (seats.empty())
        {
            seats.insert(0);
            return 0;
        }
        else
        {
            int prev = -1, dist = *seats.begin(), seat = 0;
            for (const auto& s : seats)
            {
                if (prev != -1)
                {
                    int d = ((s - prev) >> 1);
                    if (d > dist)
                    {
                        dist = d;
                        seat = prev + d;
                    }
                }
                prev = s;
            }
            if (size - 1 - *seats.rbegin() > dist) seat = size - 1;
            seats.insert(seat);
            return seat;
        }
    }
    
    void leave(int p) 
    {
        seats.erase(p);
    }
};

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom* obj = new ExamRoom(n);
 * int param_1 = obj->seat();
 * obj->leave(p);
 */

Java:

class ExamRoom {
    private TreeSet<Integer> seats;
    private int size;

    public ExamRoom(int n) {
        seats = new TreeSet<>();
        size = n;
    }
    
    public int seat() {
        if (seats.isEmpty()) {
            seats.add(0);
            return 0;
        } else {
            int dist = seats.first(), seat = 0, prev = -1;
            for (int s : seats) {
                if (prev != -1) {
                    int d = ((s - prev) >>> 1);
                    if (d > dist) {
                        dist = d;
                        seat = prev + d;
                    }
                }
                prev = s;
            }
            if (size - 1 - seats.last() > dist) seat = size - 1;
            seats.add(seat);
            return seat;
        }
    }
    
    public void leave(int p) {
        seats.remove(p);
    }
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(n);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */

Python:

class ExamRoom:

    def __init__(self, n: int):
        self.seats = []
        self.n = n


    def seat(self) -> int:
        if not self.seats:
            seat = 0
        else:
            dist, seat = self.seats[0], 0
            for i, s in enumerate(self.seats):
                if i and (d := ((s - (prev := self.seats[i - 1])) >> 1)) > dist:
                    dist, seat = d, prev + d
            if (d := self.n - 1 - self.seats[-1]) > dist:
                seat = self.n - 1
        bisect.insort(self.seats, seat)
        return seat        


    def leave(self, p: int) -> None:
        self.seats.remove(p)
        


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