Untitled

import java.util.*;

class Main {
    private int n;
    private TreeSet<Integer> seats;

    public Main(int n) {
        this.n = n;
        this.seats = new TreeSet<>();
    }

    public int seat() {
        int seat = 0;

        if (!seats.isEmpty()) {
            int maxDist = seats.first(); // Distance from 0 to first occupied seat
            Integer prev = null;

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

            // Check distance from last seat to n-1
            if (n - 1 - seats.last() > maxDist) {
                seat = n - 1;
            }
        }

        seats.add(seat);
        return seat;
    }

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

    public static void main(String[] args) {
        Main examRoom = new Main(10);
        System.out.println(examRoom.seat()); // 0
        System.out.println(examRoom.seat()); // 9
        System.out.println(examRoom.seat()); // 4
        System.out.println(examRoom.seat()); // 2
        examRoom.leave(4);
        System.out.println(examRoom.seat()); // 5
    }
}