Leetcode 855

一行N個位置，兩種操作。

seat: 每次每個同學坐在一個位置，要滿足盡量離最近的同學最遠，

leave(i), 第i個位置的人起來，保證第i的位置是有人的

sol：

将相鄰的兩個人化為一個區間，那麼每次seat的位置，就是最遠的區間的中點。需要處理邊界問題，我們可以虛拟出-1和N兩個點，初始化的時候插入(-1, N)這個區間，注意怎麼計算區間的distance的。

至于怎麼取出最大的distance的，可以使用優先隊列來實作

時間複雜度:

seat: O(lgN)

leave: O(N)

public class ExamRoom {
    int N;
    PriorityQueue<Interval> pq;
    public ExamRoom(int N) {
        this.N = N;
        this.pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.d != o2.d) return Integer.compare(o2.d, o1.d);
            return Integer.compare(o1.x, o2.x);
        });
        pq.add(new Interval(-1, N));
    }

    public int seat() {
        int s;
        Interval poll = pq.poll();
        if (poll.x == -1) s = 0;
        else if (poll.y == N) s = N - 1;
        else s = (poll.x + poll.y) / 2;
        pq.add(new Interval(poll.x, s));
        pq.add(new Interval(s, poll.y));
        return s;
    }

    public void leave(int p) {
        Interval s, e;
        s = e = null;
        ArrayList<Interval> intervals = new ArrayList<>(pq);
        for (Interval interval : intervals) {
            if (interval.y == p) s = interval;
            if (interval.x == p) e = interval;
            if (s != null && e != null) break;
        }
        pq.remove(s);
        pq.remove(e);
        pq.add(new Interval(s.x, e.y));
    }


    class Interval {
        int x, y, d;

        public Interval(int x, int y) {
            this.x = x;
            this.y = y;
            if (x == -1) d = y;
            else if (y == N) d = N - 1 - x;
            else d = (y - x) / 2;
        }
    }
}