用于选择具有最大报酬且需要最少时间的任务的数据结构

Question

关于数据结构的小问题，它允许选择具有最大奖励和最短时间的任务(当多个任务的奖励相等时)。

当我有以下任务时，考虑一个案例：

• 任务爱丽丝，会给我挣500，我需要花10时间。
• 任务鲍勃，会给我挣2000，我需要花3时间。
• 任务查理，会给我赚100的，我需要花1小时。
• 任务大卫，会给我赚1000，我需要花20的时间。
• 任务埃尔萨，会给我挣到1200，我需要花60时间。
• 任务弗兰克，会给我挣400，我需要花5时间。
• 任务格蕾丝，会给我赚400，我需要花6时间。

是否有可能得到一个具有以下结果的数据结构：

2000 | 3
1200 | 60
1000 | 20
 500 | 10
 400 | 5
 400 | 6
 100 | 1 

解释：

注意：--一旦任务完成，我就不能重获任务。

正如你所看到的，弗朗克和格蕾丝，这两个人都能挣到400英镑，工作时间分别为5小时和6小时。400 -5是第一位的，因为如果我只能做两份工作中的一份(挣400美元)，我就会选择任务F，因为这将减少我挣同样的钱。

在任务David 1000 \ 20和Elsa之间，1200 \ 60，即使任务D从技术上说是每小时挣50，而任务E每小时只挣20，我仍然会选择任务E 1200 \ 60，因为如果我只能在这两个任务中选择一份工作，我将选择1200而不是1000。

我的问题是: Java中最好的数据结构是什么？

我试过：

• HashMap

不幸的是，HashMap没有被排序，为了决定要接受哪些作业，我需要构建一个for循环来找到最大值，如果我找到多个，则再次循环这些值以得到最小值。

• 两个PriorityQueues.

当一个队列将正确地订购收入，而另一个将正确地订购时间，我将结束

Q1 = [2000, 1200, 1000, 500, 400, 400, 100]
Q2 = `[1, 3, 5, 6, 10, 20, 60]

我失去了两者之间的所有关系和“映射”，使搜索无效。

找到最大奖励和最少时间的任务(对于同等报酬的任务)最好的方法是什么？

从评论中看，这似乎是一个轻码问题或家庭作业，但事实并非如此，我只是想找出解决这个问题的最佳数据结构。

Answer 1

利用物体的力量

首先，您需要一个对象Task，试图分别维护奖励和工时的价值是错误的，不可行的。

不考虑这个特殊的问题，单独存储只有作为一个整体才有意义的价值是没有道理的。它们应该构成一个对象。

因此，您需要创建一个class，或者一个Java16 record。我将选择后者，因为这个选项要简洁得多。

public record Task(String createdBy, int reward, int hours) {}

选择数据结构

现在，让我们回到实际的问题。

我们需要一个数据结构，它允许按排序顺序使用这些任务。为此，我们可以使用https://en.wikipedia.org/wiki/Red%E2%80%93black_tree (用JDK中的TreeSet类表示)，也可以使用https://en.wikipedia.org/wiki/Heap_(data_structure) (用JDK中的PriorityQueue类表示)。

从性能角度看，维护堆比维护红黑树更不稳定.

使用堆也非常适合于任务的性质。一旦任务被消耗，它就不再有用了，因此没有必要存储它。使用Max-Heap (所有元素都较低或等于根元素)来访问最大元素，我们需要查看它的根。为了找到下一个最大元素，我们需要删除当前根。

因此，PriorityQueue将是一个最佳选择。

实现

在实例化PriorityQueue以使其能够使用对象拨号时，它们要么需要实现Comparable接口，要么需要提供Comparator。

我将选择第二个选项，因为我不认为Task有一个自然的顺序(唯一对对象有意义的排序顺序)，因为我们可能希望对它们进行不同的排序。

从Java 8开始，推荐的实现Comparator的方法是使用这个接口的静态方法。这些方法中的每一种，如comparing()和comparingInt()，都返回一个Comparator，我们可以流畅地将它们链接起来，以便根据多个条件创建一个比较器。

下面是如何使用PriorityQueue实现它

Queue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::reward)                      // the first sorting criterion - Reward
        .thenComparing(Task::hours, Comparator.reverseOrder()) // the second sorting criterion - Hours in Reversed Order
        .reversed()                                            // we need the whole thing in Descending order - from Max to Min
);
        
Collections.addAll(tasks,
    new Task("Alice", 500, 10),
    new Task("Bob", 2000, 3),
    new Task("Charlie", 100, 1),
    new Task("David", 1000, 20),
    new Task("Elsa", 1200, 60),
    new Task("Franck", 400, 5),
    new Task("Grace", 400, 6)
);
        
while (!tasks.isEmpty()) {
    // your Logic for consuming a Task goes here:
    Task next = tasks.remove();
    System.out.println(next);
}

输出：

Task[createdBy=Bob, reward=2000, hours=3]
Task[createdBy=Elsa, reward=1200, hours=60]
Task[createdBy=David, reward=1000, hours=20]
Task[createdBy=Alice, reward=500, hours=10]
Task[createdBy=Franck, reward=400, hours=5]
Task[createdBy=Grace, reward=400, hours=6]
Task[createdBy=Charlie, reward=100, hours=1]