1
class SmallestInfiniteSet {
2
  private PriorityQueue<Integer> q;
3
  private int index;
4

5
  public SmallestInfiniteSet() {
6
    q = new PriorityQueue<Integer>();
7
    index = 1;
8
  }
9

10
  public int popSmallest() {
11
    if (q.size() > 0) {
12
      return q.poll();
13
    }
14
    return index++;
15
  }
16

17
  private boolean is_in_q(int num) {
18
    for (int i : q) {
19
      if (i == num) {
20
        return true;
21
      }
22
    }
23
    return false;
24
  }
25

26
  public void addBack(int num) {
27
    if (num < index && !is_in_q(num)) {
28
      q.add(num);
29
    }
30
  }
31
}