Skip to content

855. Exam Room

  • Time:
    • Constructor: $O(1)$
    • seat(): $O(n)$
    • leave(p: int): $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class ExamRoom {
 public:
  ExamRoom(int n) : n(n) {}

  int seat() {
    if (students.empty()) {
      students.push_back(0);
      map[0] = students.begin();
      return 0;
    }

    int prevStudent = -1;
    int maxDistToClosest = 0;
    int val = 0;              // the inserted value
    list<int>::iterator pos;  // the inserted position

    for (auto it = students.begin(); it != students.end(); ++it) {
      if (prevStudent == -1) {   // We haven't insert anything before.
        maxDistToClosest = *it;  // the distance between it and the begining
        pos = it;
      } else if ((*it - prevStudent) / 2 > maxDistToClosest) {
        maxDistToClosest = (*it - prevStudent) / 2;
        val = (*it + prevStudent) / 2;
        pos = it;
      }
      prevStudent = *it;
    }

    if (n - 1 - students.back() > maxDistToClosest) {
      pos = students.end();
      val = n - 1;
    }

    map[val] = students.insert(pos, val);
    return val;
  }

  void leave(int p) {
    students.erase(map[p]);
  }

 private:
  const int n;
  list<int> students;
  unordered_map<int, list<int>::iterator> map;  // {p: student iterator}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Node {
  public Node prev;
  public Node next;
  public int value;

  public Node(int value) {
    this.value = value;
  }
}

class ExamRoom {
  public ExamRoom(int n) {
    this.n = n;
    join(head, tail);
  }

  public int seat() {
    if (head.next == tail) {
      Node node = new Node(0);
      join(head, node);
      join(node, tail);
      map.put(0, node);
      return 0;
    }

    int prevStudent = -1;
    int maxDistToClosest = 0;
    int val = 0;     // the inserted value
    Node pos = null; // the inserted position

    for (Node node = head; node != tail; node = node.next) {
      if (prevStudent == -1) {         // We haven't insert anything before.
        maxDistToClosest = node.value; // the distance between it and the begining
        pos = node;
      } else if ((node.value - prevStudent) / 2 > maxDistToClosest) {
        maxDistToClosest = (node.value - prevStudent) / 2;
        val = (node.value + prevStudent) / 2;
        pos = node;
      }
      prevStudent = node.value;
    }

    if (n - 1 - tail.prev.value > maxDistToClosest) {
      pos = tail;
      val = n - 1;
    }

    Node insertedNode = new Node(val);
    join(pos.prev, insertedNode);
    join(insertedNode, pos);

    map.put(val, insertedNode);
    return val;
  }

  public void leave(int p) {
    Node removedNode = map.get(p);
    join(removedNode.prev, removedNode.next);
  }

  private int n;
  private Node head = new Node(-1);
  private Node tail = new Node(-1);
  private Map<Integer, Node> map = new HashMap<>(); // {p: student iterator}

  private void join(Node node1, Node node2) {
    node1.next = node2;
    node2.prev = node1;
  }

  private void remove(Node node) {
    join(node.prev, node.next);
  }
}