package leetcode;

import java.util.TreeSet;

/**
 * https://leetcode.com/problems/exam-room/
 */
public class Problem855 {
    private static class ExamRoom {
        private final int n;
        private final TreeSet<Integer> set = new TreeSet<>();

        public ExamRoom(int N) {
            this.n = N;
        }

        public int seat() {
            if (set.isEmpty()) {
                set.add(0);
                return 0;
            }
            int prevIdx = 0;
            int newIdx = 0;
            int max = 0;
            for (int i : set) {
                int mid = (i - prevIdx) / 2;
                if (max < mid) {
                    max = mid;
                    newIdx = prevIdx + mid;
                }
                prevIdx = i;
            }
            if (!set.contains(0)) {
                int diff = set.first();
                if (max <= diff) {
                    newIdx = 0;
                }
            }
            if (!set.contains(n - 1)) {
                int diff = n - 1 - prevIdx;
                if (max < diff) {
                    newIdx = n - 1;
                }
            }
            set.add(newIdx);
            return newIdx;
        }

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

    public static void main(String[] args) {
        ExamRoom room = new ExamRoom(10);
//        System.out.println(room.seat()); // 0
//        System.out.println(room.seat()); // 9
//        System.out.println(room.seat()); // 4
//        System.out.println(room.seat()); // 2
//        room.leave(4);
//        System.out.println(room.seat()); // 5
//        System.out.println(room.seat()); // 7
//        System.out.println(room.seat()); // 1
//        System.out.println(room.seat()); // 3

//        System.out.println(room.seat()); // 0
//        System.out.println(room.seat()); // 9
//        System.out.println(room.seat()); // 4
//        room.leave(9);
//        System.out.println(room.seat()); // 9

//        System.out.println(room.seat()); // 0
//        System.out.println(room.seat()); // 9
//        System.out.println(room.seat()); // 4
//        room.leave(0);
//        System.out.println(room.seat()); // 0

        System.out.println(room.seat()); // 0
        System.out.println(room.seat()); // 9
        System.out.println(room.seat()); // 4
        room.leave(0);
        room.leave(4);
        System.out.println(room.seat()); // 0
        System.out.println(room.seat()); // 4
        System.out.println(room.seat()); // 2
        System.out.println(room.seat()); // 6
        System.out.println(room.seat()); // 1
        System.out.println(room.seat()); // 3
        System.out.println(room.seat()); // 5
        System.out.println(room.seat()); // 7
        System.out.println(room.seat()); // 8
        room.leave(0);
        room.leave(4);
        System.out.println(room.seat()); // 0
        System.out.println(room.seat()); // 4
    }
}

@@ -873,32 +873,64 @@
 (max %3C= diff) %7B%0A
+                    max = diff;%0A
                 
@@ -937,32 +937,32 @@
     newIdx = 0;%0A
-
                 
@@ -1291,16 +1291,16 @@
 ove(p);%0A
+
         
@@ -1310,1683 +1310,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        ExamRoom room = new ExamRoom(10);%0A//        System.out.println(room.seat()); // 0%0A//        System.out.println(room.seat()); // 9%0A//        System.out.println(room.seat()); // 4%0A//        System.out.println(room.seat()); // 2%0A//        room.leave(4);%0A//        System.out.println(room.seat()); // 5%0A//        System.out.println(room.seat()); // 7%0A//        System.out.println(room.seat()); // 1%0A//        System.out.println(room.seat()); // 3%0A%0A//        System.out.println(room.seat()); // 0%0A//        System.out.println(room.seat()); // 9%0A//        System.out.println(room.seat()); // 4%0A//        room.leave(9);%0A//        System.out.println(room.seat()); // 9%0A%0A//        System.out.println(room.seat()); // 0%0A//        System.out.println(room.seat()); // 9%0A//        System.out.println(room.seat()); // 4%0A//        room.leave(0);%0A//        System.out.println(room.seat()); // 0%0A%0A        System.out.println(room.seat()); // 0%0A        System.out.println(room.seat()); // 9%0A        System.out.println(room.seat()); // 4%0A        room.leave(0);%0A        room.leave(4);%0A        System.out.println(room.seat()); // 0%0A        System.out.println(room.seat()); // 4%0A        System.out.println(room.seat()); // 2%0A        System.out.println(room.seat()); // 6%0A        System.out.println(room.seat()); // 1%0A        System.out.println(room.seat()); // 3%0A        System.out.println(room.seat()); // 5%0A        System.out.println(room.seat()); // 7%0A        System.out.println(room.seat()); // 8%0A        room.leave(0);%0A        room.leave(4);%0A        System.out.println(room.seat()); // 0%0A        System.out.println(room.seat()); // 4%0A    %7D
 %0A%7D%0A

Solve problem 855