Data Structure for a single resource reservations

0 0 6 minutes read

Design a data structure to do reservations of future jobs on a single machine under following constraints.

Every job requires exactly k time units of the machine.
The machine can do only one job at a time.
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)
Whenever a job finishes (or its reservation time plus k becomes equal to current time), it is removed from system.

Example:

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.

Let us consider different data structures for this task. One solution is to keep all future reservations sorted in array. Time complexity of checking for conflicts can be done in O(Logn) using Binary Search, but insertions and deletions take O(n) time. Hashing cannot be used here as the search is not exact search, but a search within k time frame. 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.

Implementation:

C++

struct node
{
    int time; // reservation time
    struct node *left, *right;
};
 
// A utility function to create a new BST node
node* newNode(int item)
{
    node* temp = new 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  */
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;
}

C

// 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;
}

Java

// 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

Python3

class Node:
    def __init__(self, time):
        self.time = time
        self.left = None
        self.right = None
 
# A utility function to create a new BST node
def newNode(item):
    temp = 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  """
def insert(root, time, k):
    """ If the tree is empty, return a new node """
    if root is None: 
        return newNode(time)
 
    # Check if this job conflicts with existing
    # reservations
    if (time-k < root.time and 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 surajrasr7277

C#

// A BST node to store future reservations
public class Node {
    public int time; // reservation time
    public Node left, right;
 
    public Node(int t)
    {
        time = t;
          left = right = null;
    }
};
 
// 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 Abhijeet Kumar(abhijeet19403)

Javascript

// JavaScript program for the above approach
class node{
    constructor(item){
        this.time = data;
        this.left = null;
        this.right = null;
    }
}
 
// a utility function to create a new BST node
function newNode(item){
    return new node(item);
}
 
/* 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  */
function insert(root, time, k){
    // if the tree is empty, return a new node
    if(root == null) return newNode(time);
     
    // check if this job confilicts 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 YASH AGARWAL(YASHAGARWAL2852002)

Time complexity: O(h), where h is the height of the tree.
Space complexity: O(h) for recursive call stack.

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.
This question is adopted from this MIT lecture.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!