java - 具有独立期限的任务调度算法

Question

我有 n 个任务，每个任务都有特定的截止日期和完成所需的时间。但是，我无法在截止日期前完成所有任务。我需要以这样一种方式安排这些任务，以尽量减少拍摄时间的任务截止日期。考虑这种情况(左边的值是截止日期，右边的值是任务花费的时间):
2 2
1 1
4 3
这三个任务可以像这样最佳地完成:

时间 1:任务 2 - 任务 1 完成；任务 2 的 0 过冲
时间 2:任务 1
时间 3:任务 1 - 任务 2 完成；任务 1 的 1 个超调
时间 4:任务 3
时间 5:任务 3
时间 6:任务 3 - 任务 3 完成； 3 任务 3 的超调

为此我需要一个更快的算法；我的目标是找到所有超调的最大超调(在上面的例子中是 3)。现在，我正在根据截止日期对任务进行排序，但速度并不快，因为添加新任务时，我应该对整个列表进行排序。还有其他办法吗？

---

根据 Lawrey 的建议，我正在使用 PriorityQueue，但它没有给我准确的排序。这是我的代码:

class Compare2DArray implements Comparator<int[]> {
public int compare(int a[], int b[]) {
    for (int i = 0; i < a.length && i < b.length; i++)
        if (a[i] != b[i])
            return a[i] - b[i];
    return a.length - b.length;
}
}

public class MyClass{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int numberOfInputs= scan.nextInt();
        PriorityQueue<int[]> inputsList = new PriorityQueue<int[]>(numberOfInputs,new Compare2DArray());
        for (int i = 0; i < numberOfInputs; i++) {
            int[] input = new int[2];
            input[0] = scan.nextInt();
            input[1] = scan.nextInt();
            inputsList.add(input);

        }
    }

但是这是对这个数组队列进行排序

2 2
1 1
4 3
10 1
2 1

作为

1 1
2 1
4 3
10 1
2 2

而不是

1 1
2 1
2 2
4 3
10 1

相同的比较器在列表排序上工作得很好。我没有弄错 PriorityQueue

Answer 1

优先级队列是使用堆实现的。因此，当您扫描优先级队列的元素时，它不能保证它会按排序顺序为您提供所有元素。这就是您没有获得所需的排序数组的原因。

我也遇到了同样的问题。我最终在 C++ 中使用了 multimap。但时间复杂度仍然没有太大改善。