algorithm - 作业之间的最小间隔

Question

我正在尝试解决一个问题，即最小化数组中给定的作业之间的时间间隔总和。作业结构如下:

struct Job{ int start, end; };

函数原型(prototype)为:

int impatientBob(Job jobs[], int n, int k)

作业不能重叠，我必须从数组中选择 k 个，如果不可能则返回 -1。此外，数组按作业的结束时间排序，时间以分钟为单位。我没有任何好主意，因为我对动态规划还是很陌生。

Answer 1

我能想到的一个解决方案是复杂度 O(n^2 * k)。

你可以这样做(以下只是一个伪代码):

int minTimeIntervals(current_index, last_taken, k){
    if(k == 0) return 0 // if you already taken k jobs then you're done
    if(current_index == n) return BIG NUMBER // if you reached the end of the jobs without taking k jobs, then this is an invalid solution. Set it to a big number so when you minimize it's always neglected.

    check if the given state is memorized and has been calculated before.

    decision1 = minTimeIntervals(current_index + 1, last_taken, k) // Choose not to take the current job and move to the next.
    if(start time of current job > end time of last taken job){
        // Choose to take the current job of that's valid (i.e they don't intersect)
        decision2 = minTimeIntervals(current_index + 1, current_index, k-1) + difference of time between last_taken and current_index
    }
    return minimum of decision1 and decision2 and memorize the answer for the given state.
}

编辑:添加更具体的代码。

int memo[N][N][K]; // Should be initialized with -1

int minTimeIntervals(int current_index, int last_taken, int k){
    if(k == 0) return 0;
    if(current_index == N) return 1<<27; // 2^27, Just a big number.

    if(last_taken != -1 && memo[current_index][last_taken][k] != -1) return memo[current_index][last_taken][k];

    int decision1 = minTimeIntervals(current_index + 1, last_taken, k);
    int decision2 = 1<<27;
    if(last_taken == -1 || jobs[current_index].start >= jobs[last_taken].end){
        decision2 = minTimeIntervals(current_index + 1, current_index, k - 1) + (jobs[current_index].start - jobs[last_taken].end);
    }
    int result = min(decision1, decision2);
    memo[current_index][last_taken][k] = result;
    return result;
}

这段代码所做的是，对于给定的状态 (current_index, last_taken, k)，它计算答案并将其存储在 memo[current_index][last_taken][k] 中。

数组 memo 应该用一些永远不可能是有效答案的值(例如 -1)来初始化。现在，如果 memo[i][j][k] 的值是 -1，这意味着我们之前没有计算状态 (i,j,k)，所以我们计算并存储它在 memo[i][j][k] 中。

如果对于某些给定状态 (i,j,k)，memo[i][j][k] 中的值是某个非负值(例如 5)，这意味着我们之前处理过这个状态，答案是5所以直接返回这个答案，不重复计算。

最后一个棘手的部分是，当您选择第一份工作时，您没有以前的工作来计算时差。为此，我们将 last_taken 设置为 -1，这样我们就知道这是第一份工作，我们不必计算 current_index 和 last_taken 之间的时间差。

现在你的主函数 impatientBob 应该做一些初始化工作，比如将 memo 值设置为 -1，然后调用函数 minTimeIntervals(0, -1, k ) 这意味着你是从第一份工作开始的，你之前没有做过任何工作，你还需要做 k 份工作。