Data Structure for a single resource reservations - GeeksforGeeks

Data Structure for a single resource reservations - GeeksforGeeks
Design a data structure to do reservations of future jobs on a single machine under following constraints.
1) Every job requires exactly k time units of the machine.
2) The machine can do only one job at a time.
3) Time is part of the system. Future Jobs keep coming at different times. Reservation of a future job is done only if there is no existing reservation within k time frame (after and before)
4) Whenever a job finishes (or its reservation time plus k becomes equal to current time), it is removed from system.

The idea is to use Binary Search Tree to maintain set of reserved jobs. For every reservation request, insert it only when there is no conflicting reservation. While inserting job, do “within k time frame check”. If there is a k distant node on insertion path from root, then reject the reservation request, otherwise do the reservation.

Deletion of job is simple BST delete operation.

A normal BST takes O(h) time for insert and delete operations. We can use self-balancing binary search trees like AVL, Red-Black, .. to do both operations in O(Log n) time.

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;

}

Read full article from Data Structure for a single resource reservations - GeeksforGeeks