考场就座

/*
思路：
1. 使用一个 TreeSet 记录已经被占据的座位，以保持有序。
2. 每次调用 seat() 时，找到能够使离他最近的人之间的距离最大化的座位。
3. 使用 leave(p) 函数将座位 p 标记为空。
*/

import java.util.TreeSet;

public class ExamRoom {
    private int N;
    private TreeSet<Integer> seats;

    public ExamRoom(int N) {
        this.N = N;
        this.seats = new TreeSet<>();
    }

    public int seat() {
        if (seats.isEmpty()) {
            seats.add(0);
            return 0;
        }

        int maxDist = seats.first();
        int seat = 0;
        Integer prev = null;

        for (int s : seats) {
            if (prev != null) {
                int dist = (s - prev) / 2;
                if (dist > maxDist) {
                    maxDist = dist;
                    seat = prev + dist;
                }
            }
            prev = s;
        }

        if (N - 1 - seats.last() > maxDist) {
            seat = N - 1;
        }

        seats.add(seat);
        return seat;
    }

    public void leave(int p) {
        seats.remove(p);
    }
}