1

n 個のタスクのタスク スケジューリング問題は、欲張りアルゴリズムによって解決されます。さまざまなコーディングの課題で、この特定の種類の問題に遭遇しました。これは、最大オーバーシュートの最小値を動的に見つけることを要求します。そのうちの 1 つを以下に示します。

インタビュー通りの問題:

今日やらなければならないタスクの長いリストがあります。タスク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 に答える