设计数据结构以在以下约束下在一台计算机上保留将来的作业。
1)每个作业都需要机器的k个时间单位。
2)机器一次只能执行一项工作。
3)时间是系统的一部分。未来的工作会在不同的时间来临。仅当在k个时间段内(之后和之前)不存在现有预约时, 才保留将来的工作。
4)每当作业完成时(或其保留时间加k等于当前时间), 就会将其从系统中删除。
例子:
Let time taken by a job (or k) be = 4At 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 45Jobs at 30, 35 and 45 are reserved, but at 17cannot 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.
让我们考虑此任务的不同数据结构。
一种解决方案是使所有将来的保留按数组排序。检查冲突的时间复杂度可以在O(Logn)中使用二元搜寻, 但是插入和删除操作需要O(n)时间。
【单个资源预留的数据结构】散列此处的搜索不是精确搜索, 而是k个时间范围内的搜索, 因此无法在此处使用。
这个想法是使用二进制搜索树维护一组保留的作业。对于每个预订请求, 仅在没有冲突的预订时才插入。插入作业时, 请执行” 在k个时间范围内检查” 。如果在从根到根的插入路径上有k个遥远的节点, 则拒绝保留请求, 否则进行保留。
//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;
}
删除工作很简单BST删除操作。
正常的BST花费O(h)时间进行插入和删除操作。我们可以使用自平衡二进制搜索树, 例如AVL, 红黑, ..在O(Log n)时间内执行这两项操作。
这个问题来自这个麻省理工学院讲座。
本文作者:拉杰夫。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- 数据结构综合列表
- 字典和拼写检查器的数据结构()
- 数据科学生命周期详细指南
- Python中机器学习的数据预处理
- 数据挖掘中数据源的类型详细介绍
- 数据挖掘基本概念详细介绍
- R中的DataFrame操作详细指南
- 编译器中的数据流分析简要指南
- 数据通信中的传输障碍详细指南