1

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

面试街题：

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

您已经意识到实际上不可能在截止日期前完成所有任务，因此您决定完成它们，以便将任务完成时间超过其截止日期的最大量减至最少。

我的方法

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

4

2 回答 2

2

首先，您需要证明给定一组任务(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));
    }
}
于 2013-03-11T15:41:42.670 回答
1 
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);
     }
  }
}
于 2016-01-22T22:06:38.853 回答