Dyanmic任务调度专访街 [英] Dyanmic Task Scheduling Interview Street
问题描述
对于n任务的任务调度问题是贪心算法解决。我也遇到过这种特殊形式的各种编码的挑战问题，这要求找出最小和最大超调动态的。其中之一是表示如下：
The task scheduling problem for n tasks is solved by greedy algorithm. I have encountered this particular sort of problem in various coding challenges which asks to find out minimum of maximum overshoot dynamically. One of them is stated below:
专访街问题：
您有您需要今天做任务，一个长长的清单。任务的我的是由你必须完成它（DI）的最后期限，并分钟它会带你完成任务数（MI）指定。您无需填写一气的任务。你可以完成它的一部分，切换到另一个任务，然后切换回来。
You have a long list of tasks that you need to do today. Task i is specified by the deadline by which you have to complete it (Di) and the number of minutes it will take you to complete the task (Mi). You need not complete a task at a stretch. You can complete a part of it, switch to another task and then switch back.
您已经意识到，它可能不是真正能够完成所有的任务，他们的最后期限，所以你决定完成他们，使通过该任务的完成时间过冲其限期最大量最小化。
You've realized that it might not actually be possible complete all the tasks by their deadline, so you have decided to complete them so that the maximum amount by which a task's completion time overshoots its deadline is minimized.
我的方法
现在考虑的一个中间阶段，我们已经发现的 I-1 的任务的解决方案，并已安排他们有序。我们还存储了曾与最大过冲任务的索引的的i-1 的任务说的 maxLate 的。在* I *个任务到来后，我们检查，如果D [我的] LT; D [ maxlate 的]那么新maxLate将任第i个任务的老maxLate。 我很困惑的情况下，当D [我]> D [ maxlate 的。是一种线性扫描必要对于这种情况？ 也建议的良好的数据结构更新，新名单，并保持他们的排序顺序。 感谢您的帮助。
Now consider an intermediate stage where we have found the solution for i-1 tasks and have arranged them in sorted order. We have also stored the index of the task which had the maximum overshoot with i-1 tasks say maxLate. After the arrival of the *i*th task we check if D[i] < D[maxlate] then the new maxLate will be either old maxLate of the ith task. I am confused for the case when D[i] > D[maxlate]. Is a linear scan necessary for this case? Also suggest a good data structure for updating the new list and keeping them in sorted order. Thanks for your help.
推荐答案
首先，你需要证明给定一组任务（m_i，d_i），最好的安排是根据他们的最后期限完成的工作，即应急工作第一。
First of all, you need to prove that given a set of task (m_i, d_i), the best schedule is finish the jobs according to their deadlines, i.e. emergent jobs first.
和问题是等价于：
for each job in original order:
dynamically insert this job (m_i, d_i) into a sorted job_list
query max{ (sum(m_k for all k <= n) - d_n) for all n in job_list }
这为O（N ^ 2），其中N是工作数量，这是越来越接受采访街太慢算法运行。但是，我们可以使用一些高级的数据结构，加快插入和查询操作。
This algorithm run in O(N^2) where N is the number of jobs, which is too slow for getting accepted in interview street. However, we can use some advanced data structure, to speed up the insert and query operation.
我使用段树懒更新解决O（NlgN）时间这个问题，这是我的code
I use a segment tree with lazy update to solve this problem in O(NlgN) time, and here's my code
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
class SegTree
{
public:
SegTree(int left, int right, const vector<int>& original_data)
{
this->left = left;
this->right = right;
this->lazy_flag = 0;
left_tree = right_tree = NULL;
if (left == right)
{
this->value = this->max_value = original_data[left];
}
else
{
mid = (left + right) / 2;
left_tree = new SegTree(left, mid, original_data);
right_tree = new SegTree(mid + 1, right, original_data);
push_up();
}
}
void modify(int left, int right, int m_value)
{
if (this->left == left && this->right == right)
{
leaf_modify(m_value);
}
else
{
push_down();
if (left <= mid)
{
if (right >= mid + 1)
{
left_tree->modify(left, mid, m_value);
right_tree->modify(mid + 1, right, m_value);
}
else
{
left_tree->modify(left, right, m_value);
}
}
else
{
right_tree->modify(left, right, m_value);
}
push_up();
}
}
int query(int left, int right)
{
if (this->left == left && this->right == right)
{
return this->max_value;
}
else
{
push_down();
if (left <= mid)
{
if (right >= mid + 1)
{
int max_value_l = left_tree->query(left, mid);
int max_value_r = right_tree->query(mid + 1, right);
return max(max_value_l, max_value_r);
}
else
{
return left_tree->query(left, right);
}
}
else
{
return right_tree->query(left, right);
}
}
}
private:
int left, right, mid;
SegTree *left_tree, *right_tree;
int value, lazy_flag, max_value;
void push_up()
{
this->max_value = max(this->left_tree->max_value, this->right_tree->max_value);
}
void push_down()
{
if (this->lazy_flag > 0)
{
left_tree->leaf_modify(this->lazy_flag);
right_tree->leaf_modify(this->lazy_flag);
this->lazy_flag = 0;
}
}
void leaf_modify(int m_value)
{
this->lazy_flag += m_value;
this->max_value += m_value;
}
};
vector<int> vec_d, vec_m, vec_idx, vec_rank, vec_d_reorder;
int cmp(int idx_x, int idx_y)
{
return vec_d[idx_x] < vec_d[idx_y];
}
int main()
{
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++)
{
int d, m;
scanf("%d%d", &d, &m);
vec_d.push_back(d);
vec_m.push_back(m);
vec_idx.push_back(i);
}
sort(vec_idx.begin(), vec_idx.end(), cmp);
vec_rank.assign(T, 0);
vec_d_reorder.assign(T, 0);
for (int i = 0; i < T; i++)
{
vec_rank[ vec_idx[i] ] = i;
}
for (int i = 0; i < T; i++)
{
vec_d_reorder[i] = -vec_d[ vec_idx[i] ];
}
// for (int i = 0; i < T; i++)
// {
// printf("m:%d\td:%d\tidx:%d\trank:%d\t-d:%d\n", vec_m[i], vec_d[i], vec_idx[i], vec_rank[i], vec_d_reorder[i]);
// }
SegTree tree(0, T-1, vec_d_reorder);
for (int i = 0; i < T; i++)
{
tree.modify(vec_rank[i], T-1, vec_m[i]);
int ans = tree.query(0, T-1);
printf("%d\n", max(0,ans));
}
}
这篇关于Dyanmic任务调度专访街的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
