class NumberContainer {

  val indexToNumber = mutableMapOf<Int, Int>()
  val numberToIndexes = mutableMapOf<Int, PriorityQueue<Int>>()

  // n == count of indexes
  // m == count of numbers
  // O(n) + O(logn)
  fun insertOrReplace(index: Int, number: Int) {
    if (index in indexToNumber) {
      val oldNumber = indexToNumber.getValue(index)
      numberToIndexes.getValue(oldNumber).remove(index)
    }
    indexToNumber[index] = number
    numberToIndexes.getOrPut(number) { PriorityQueue() } += index
  }

  // O(1)
  fun findSmallestIndex(number: Int): Int {
    return numberToIndexes[number]?.poll() ?: -1
  }

  // O(n)
  fun deleteNumber(number: Int) {
    if (number !in numberToIndexes) return
    for (index in numberToIndexes.getValue(number)){
      indexToNumber -= index
    }
    numberToIndexes -= number
  }
}

// Question details
// You're given an interface of a Dynamic Tree, your task is to write an
// implementation according to the interface docstrings. You can change the syntax according to a language of your choice, feel free to use any helper methods or fields.
// Implement the methods of the following Tree class.

data class TreeNode<T> {
  TreeNode parent = null;
  T item;
  // New fields if required.
}

class Tree<T> {
  // Creates Tree instance in which the number of nodes can not exceed capacity.
  // The tree should already have a single node: its root.
  Tree(int capacity) {}

  // Returns the number of nodes.
  int size() {}

  // Returns the root of the tree.
  TreeNode getRoot() {}

  // Creates a node that is attached to a parent node that already exists.
  TreeNode createNode(TreeNode parent) {}

  // Returns a random node in the Tree. Each Tree's node has an equal probability to
  // be selected.
  TreeNode getRandomNode() {}
}

// My code

data class TreeNode(val parent: TreeNode?, children: MutableList<TreeNode>)

class Tree(private val capacity: Int) {
  var root = TreeNode(null, mutableListOf()) // arraylist
  var size = 1
  val nodes = mutableListOf(root)
  val leaves = mutableListOf(root)
  val random = Random()

  fun size(): Int = size

  fun getRoot(): TreeNode = root

  fun createNode(parent: TreeNode): TreeNode {
    if (size == capacity) throw IllegalStateException()
    val node = TreeNode(
      parent,
      mutableListOf())
    )
    parent.children += node
    nodes += node
    size++
    return node
  }

  fun getRandomNode(): TreeNode {
    val index = random.getInt(nodes.size) // [0-nodes.size)
    return nodes[index]
  }

  fun getRandomLeaf(): TreeNode {
    val leaves = nodes.filter { }
  }
}

// Time: O(n)
buildTree(int n) {
  tree = new Tree(n); // Time: O(1)
  for (i=0; i<n-1; i++) { // Time: O(n)
    parent = tree.getRandomNode(); // Time: O(1)
    tree.createNode(parent); // Time: O(1)
  }
}

We are given on-call rotation schedule for multiple people by: their name, start time and end time of the rotation:
Abby 1 10
Ben 5 7
Carla 6 12
David 15 17
Abby 8 13

Question: Giving a T time, return all people names who are oncall during that time.
So for T = 9; Expected output: [Abby, Carla]

data class Rotation(name: String, start: Int, end: Int)

// O(n)
// T = 9
// filtered in: [Abby, Carla, Abby]
// filtered out: [Ben, David,
// Abby - 1 <= 9, 10 >= 9
// 7 >= 9
// 6 9
// 6 <= 9 T 12 >= 9 T
// 15 <= 9 F
// 8 <= 9 T 13 >= 9 T
fun currentlyOncall(rotations: List<Rotation>, time: Int): Set<String> {
  return rotations.filter { it.start <= time && it.end >= time }.map { it.name }.toSet()
}

Given on-call rotation schedule for multiple people by: their name, start time and end time of the rotation:

Abby 1 10
Ben 5 7
Carla 6 12
David 15 17

Your goal is to return rotation table without overlapping periods representing who is on call during that time. Return "Start time", "End time" and list of on-call people:

1 5 Abby
5 6 Abby, Ben
6 7 Abby, Ben, Carla
7 10 Abby, Carla
10 12 Carla
15 17 David


  |------Abby------|
          |----Carla---|
      |--Ben--|              |-David-|
--1---5---6---7---10---12---15-------17--

// [(1, true, Abby), (5, true, Ben), (7, false, Ben), (10, false, Abby)
//

data class TableRow(start: Int, end: Int, names: List<String>>)

fun createRotationTable(rotations: List<Rotation>): List<TableRow> {
  val intermediate: List<Triple<Int, Boolean, Name>> = rotations.flatMap { listOf(it.start to true to it.name, it.end to false to it.name) }.sortedBy { it.start }
  val result = mutableListOf()
  for (
  return result
}