假设我们要执行一组n个作业，每个作业都花费单位时间。在任何时候，我们都可以只担任一项工作。 i，1<=i<=n个工作只有在不迟于截止日期执行的情况下才能为我们赚取利润。
如果存在至少一个序列，允许该组中的每个作业不迟于其截止日期执行，我们可以使一组作业可行。 “最早截止日期优先”是可行的。
[表明贪婪算法是最优的：在每个步骤中，将尚未获得考虑的那些利润最高的工作添加进去，前提是所选的工作集仍然可行。
首先必须做的第一件事：首先表明，总是可以重新安排两个可行的序列（一个由Greedy计算），这样就可以同时调度两个序列共有的每个作业。这个新序列可能包含空白。
UPDATE
我创建了一个似乎证明算法不正确的示例：
承担4个工作：
[如果我们首先使用获利最高的贪婪算法，那么我们只会获得作业B和C。但是，如果我们首先执行截止日期，那么我们将获得所有作业，并且订单为CDB
不确定我是否以正确的方式解决了这个问题，因为我创建了一个示例来反驳问题的意图
事实上，“最早的截止日期优先”，“最高的利润优先”或“最高的利润/持续时间都不是正确的算法...
承担2个工作：
然后“最早的截止日期优先”未能获得正确的答案。正确答案是B。
假设另外5个工作：
然后“最高利润优先”未能获得正确答案。正确答案是BCDE。
假设另外4个工作：
然后“最高利润/持续时间优先”未能获得正确答案。正确答案是BC（感谢@dognose的反例，请参阅评论）。
一种正确的算法是动态编程：
按截止日期的先后顺序递增。 dp[i][j] = k表示在前i个工作中并且在j个时间单位内，我们可以获得k最高利润。然后最初是dp[0][0] = 0。
职位信息存储在3个数组中：利润存储在profit[i], 1<=i<=n中，持续时间存储在time[i], 1<=i<=n中，期限存储在deadline[i], 1<=i<=n中。
// sort by deadline in ascending order
...
// initially 2 dimension dp array are all -1, -1 means this condition unreachable
...
dp[0][0] = 0;
int maxDeadline = max(deadline); // max value of deadline
for(int i=0;i<n;i++) {
for(int j=0;j<=maxDeadline;j++) {
// if do task i+1 satisfy deadline condition, try to update condition for "within the first i+1 jobs, cost j+time[i+1] time units, what's the highest total profit will be"
if(dp[i][j] != -1 && j + time[i+1] <= deadline[i+1]) {
dp[i+1][j+time[i+1]] = max(dp[i+1][j+time[i+1]], dp[i][j] + profit[i+1]);
}
}
}
// the max total profit can get is max value of 2 dimension dp array
DP算法的时间/空间复杂度（n*m，n是作业计数，m是最大期限）在很大程度上取决于有多少个作业和最大期限。如果n和/或m很大，则可能难以获得答案，而对于常见用途，它将很好地工作。
这个问题看起来像Job Shop Scheduling，它是NP完全的（这意味着没有最优的贪婪算法-尽管专家从70年代开始就试图找到一个）。 Here's a video该用例的更高级形式，正在通过Greedy算法和本地搜索来解决。
[如果我们假设您的用例确实可以简化为Job Shop Scheduling，那么有很多优化算法可以提供帮助，例如元启发法（包括禁忌搜索和模拟退火等本地搜索），（M）IP，动态编程，约束编程，...之所以选择如此之多，是因为没有一个是完美的。我更喜欢元启发法，因为它们在我所看到的所有研究挑战中都超越了其他方法。
该问题称为有期限的作业排序，可以通过两种基于贪婪策略的算法来解决：