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.
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.
[ad type=”banner”]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.
[pastacode lang=”c” manual=”%2F%2F%20A%20BST%20node%20to%20store%20future%20reservations%0Astruct%20node%0A%7B%0A%20%20%20%20int%20time%3B%20%2F%2F%20reservation%20time%0A%20%20%20%20struct%20node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20BST%20node%0Astruct%20node%20*newNode(int%20item)%0A%7B%0A%20%20%20%20struct%20node%20*temp%20%3D%0A%20%20%20%20%20%20%20%20(struct%20node%20*)malloc(sizeof(struct%20node))%3B%0A%20%20%20%20temp-%3Etime%20%3D%20item%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20BST%20insert%20to%20process%20a%20new%20reservation%20request%20at%0A%20%20%20a%20given%20time%20(future%20time).%20%20This%20function%20does%0A%20%20%20reservation%20only%20if%20there%20is%20no%20existing%20job%20within%0A%20%20%20k%20time%20frame%20of%20new%20job%20%20*%2F%0Astruct%20node*%20insert(struct%20node*%20root%2C%20int%20time%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F*%20If%20the%20tree%20is%20empty%2C%20return%20a%20new%20node%20*%2F%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%20return%20newNode(time)%3B%0A%20%0A%20%20%20%20%2F%2F%20Check%20if%20this%20job%20conflicts%20with%20existing%0A%20%20%20%20%2F%2F%20reservations%0A%20%20%20%20if%20((time-k%20%3C%20root-%3Etime)%20%26%26%20(time%2Bk%20%3E%20root-%3Etime))%0A%20%20%20%20%20%20%20%20return%20root%3B%0A%20%0A%20%20%20%20%2F*%20Otherwise%2C%20recur%20down%20the%20tree%20*%2F%0A%20%20%20%20if%20(time%20%3C%20root-%3Etime)%0A%20%20%20%20%20%20%20%20root-%3Eleft%20%20%3D%20insert(root-%3Eleft%2C%20time%2C%20k)%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20root-%3Eright%20%3D%20insert(root-%3Eright%2C%20time%2C%20k)%3B%0A%20%0A%20%20%20%20%2F*%20return%20the%20(unchanged)%20node%20pointer%20*%2F%0A%20%20%20%20return%20root%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]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.
[ad type=”banner”]