algorithm - 动态任务调度面试街

Question

n 个任务的任务调度问题通过贪心算法求解。我在各种编码挑战中遇到过这类特殊问题，这些挑战要求动态找出最大过冲的最小值。其中之一如下:

面试街问题:

您有一长串今天需要完成的任务。任务 i 由您必须完成的截止日期 (Di) 和完成任务所需的分钟数 (Mi) 指定。您无需一口气完成一项任务。您可以完成其中的一部分，切换到另一个任务，然后再切换回来。

您已经意识到实际上可能无法在截止日期前完成所有任务，因此您决定完成这些任务，以使任务完成时间超出截止日期的最大量最小化。

我的方法

现在考虑一个中间阶段，我们找到了 i-1 个任务的解决方案，并将它们按排序顺序排列。我们还存储了与 i-1 个任务有最大超调的任务的索引，比如 maxLate。在第 *i* 个任务到达后，我们检查是否 D[i] < D[maxlate] 那么新的 maxLate 将是第 i 个任务的旧 maxLate。我对 D[i] > D[maxlate] 的情况感到困惑。这种情况是否需要线性扫描？还建议一个良好的数据结构来更新新列表并保持它们的排序顺序。感谢您的帮助。

Answer 1

首先，您需要证明给定一组任务(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操作。

我使用 segment tree with lazy update在 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));
    }
}