Estructura de datos para reservas de un solo recurso

Diseñe una estructura de datos para hacer reservas de trabajos futuros en una sola máquina bajo las siguientes restricciones. 

1. Cada trabajo requiere exactamente k unidades de tiempo de la máquina. 
2. La máquina solo puede hacer un trabajo a la vez.  
3. El tiempo es parte del sistema. Los trabajos futuros siguen llegando en diferentes momentos. La reserva de un trabajo futuro se realiza solo si no hay una reserva existente dentro del marco de tiempo k (antes y después) 
4. Cada vez que finaliza un trabajo (o su tiempo de reserva más k se vuelve igual al tiempo actual), se elimina del sistema. 

Ejemplo:

Let time taken by a job (or k) be = 4

At time 0: Reservation request for a job at time 2 in 
           future comes in, reservation is done as machine 
           will be available (no conflicting reservations)
Reservations {2}

At time 3: Reservation requests at times 15, 7, 20 and 3.
           Job at 7, 15 and 20 can be reserved, but at 3 
           cannot be reserved as it conflicts with a 
           reserved at 2.
Reservations {2, 7, 15, 20}

At time 6: Reservation requests at times 30, 17, 35 and 45
           Jobs at 30, 35 and 45 are reserved, but at 17  
           cannot be reserved as it conflicts with a reserved 
           at 15.
Reservations {7, 15, 30, 35, 45}.
Note that job at 2 is removed as it must be finished by 6.

Consideremos diferentes estructuras de datos para esta tarea. Una solución es mantener todas las reservas futuras ordenadas en una array. La complejidad del tiempo de la verificación de conflictos se puede realizar en O (Inicio de sesión) utilizando la búsqueda binaria , pero las inserciones y eliminaciones toman O (n) tiempo. Hashing no se puede usar aquí ya que la búsqueda no es una búsqueda exacta, sino una búsqueda dentro de un marco de tiempo k. La idea es utilizar el árbol de búsqueda binaria para mantener un conjunto de trabajos reservados. Para cada solicitud de reserva, insértela solo cuando no haya ninguna reserva en conflicto. Mientras inserta el trabajo, haga «verificación dentro de k marco de tiempo». Si hay un Node distante en la ruta de inserción desde la raíz, rechace la solicitud de reserva; de lo contrario, realice la reserva. 

Implementación:

// A BST node to store future reservations
struct node
{
    int time; // reservation time
    struct node *left, *right;
};
 
// A utility function to create a new BST node
struct node *newNode(int item)
{
    struct node *temp =
        (struct node *)malloc(sizeof(struct node));
    temp->time = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
/* BST insert to process a new reservation request at
   a given time (future time).  This function does
   reservation only if there is no existing job within
   k time frame of new job  */
struct node* insert(struct node* root, int time, int k)
{
    /* If the tree is empty, return a new node */
    if (root == NULL) return newNode(time);
 
    // Check if this job conflicts with existing
    // reservations
    if ((time-k < root->time) && (time+k > root->time))
        return root;
 
    /* Otherwise, recur down the tree */
    if (time < root->time)
        root->left  = insert(root->left, time, k);
    else
        root->right = insert(root->right, time, k);
 
    /* return the (unchanged) node pointer */
    return root;
}

// A BST node to store future reservations
class Node {
    int time; // reservation time
    Node left, right;
 
    Node(int time)
    {
        super();
        this.time = time;
    }
};
 
// A utility function to create a new BST node
Node newNode(int item)
{
    Node temp = new Node(item);
    return temp;
}
 
/* BST insert to process a new reservation request at
a given time (future time). This function does
reservation only if there is no existing job within
k time frame of new job */
Node insert(Node root, int time, int k)
{
    /* If the tree is empty, return a new node */
    if (root == null)
        return newNode(time);
 
    // Check if this job conflicts with existing
    // reservations
    if ((time - k < root.time) && (time + k > root.time))
        return root;
 
    /* Otherwise, recur down the tree */
    if (time < root.time)
        root.left = insert(root.left, time, k);
    else
        root.right = insert(root.right, time, k);
 
    /* return the (unchanged) node pointer */
    return root;
}
 
// This code is contributed by jainlovely450

La eliminación del trabajo es una operación simple de eliminación de BST . Un BST normal toma tiempo O(h) para las operaciones de inserción y eliminación. Podemos usar árboles de búsqueda binarios autoequilibrados como AVL , Red-Black , .. para realizar ambas operaciones en tiempo O (Log n). 
Esta pregunta se adoptó de esta conferencia del MIT.