n个任务的任务调度问题是由贪婪算法求解。 我也遇到过这种特殊形式的各种编码的挑战问题，询问动态找出最大过冲的最小值。 其中一人的陈述如下：
面试街问题：
您有您今天需要完成的任务的一长串。 我的任务是通过你必须完成它（DI）的截止时间和分钟的它会带你完成任务（MI）指定的号码。 您无需填写一气的任务。 你可以完成它的一部分，切换到另一个任务，然后切换回来。
你已经意识到，它可能不是真正能够完成他们的最后期限的所有任务，所以你已经决定完成它们，以便通过该任务的完成时间过冲其限期最大的量最小化。
我的方法
现在，假设我们已经找到了I-1任务的解决方案并按照顺序安排了他们的中间阶段。 我们还存储其中有最大超调与I-1任务说maxLate的任务指标。 的到来后* I *我们检查，如果d [I] <d [maxlate]那么新maxLate位将是第i个任务的老maxLate个任务。 我感到困惑的情况下，当d [I]> d [maxlate]。 是线性的这种情况下，扫描必要吗？ 还建议更新新的列表，并让他们在有序良好的数据结构 。 谢谢你的帮助。
首先，你需要证明给定一组任务(m_i, d_i)最佳的时间表是首先根据其最后期限完成的工作，即应急工作。
而问题是等价于：
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是工作数量，这是在采访中街市场接受速度太慢运行。 但是，我们可以使用一些高级的数据结构，加快insert和query操作。
我用一个懒更新线段树解决O（NlgN）时间这个问题，这是我的代码
#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));
}
}
class Schedule {
int deadLine = 0;
int taskCompletionTime = 0;
int done = 0;
Schedule(int deadline, int taskCompletionTime) {
this.deadLine = deadline;
this.taskCompletionTime = taskCompletionTime;
}
}
class TaskScheduler {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int max = 0;
ArrayList<Schedule> sch = new ArrayList<Schedule>();
for(int i = 0; i < n; i++) {
int deadLine = in.nextInt();
int taskCompletionTime = in.nextInt();
Schedule s = new Schedule(deadLine, taskCompletionTime);
int j = i-1;
while(j >= 0 && sch.get(j).deadLine > s.deadLine) {
Schedule s1 = sch.get(j);
if(s1.deadLine <= s.deadLine) break;
s1.done += s.taskCompletionTime;
max = Math.max(max, s1.done - s1.deadLine);
j--;
}
sch.add(j+1, s);
if(j < 0)
s.done = s.taskCompletionTime;
else
s.done = sch.get(j).done + s.taskCompletionTime;
max = Math.max(max, s.done - s.deadLine);
System.out.println(max);
}
}
}
