[FIXED] Data Structure for chosing a Task having Max Reward and requering Min amount of Time

Issue

Small question regarding a Data structure which would allow to choose a Task having the maximum rewards and with the minimum amount of time (when rewards of several tasks are equal).

Considering a case when I have the following Tasks:

• Task Alice, will earn me 500, I need to spend 10 hours.
• Task Bob, will earn me 2000, I need to spend 3 hours.
• Task Charlie, will earn me 100, I need to spend 1 hour.
• Task David, will earn me 1000, I need to spend 20 hours.
• Task Elsa, will earn me 1200, I need to spend 60 hours.
• Task Franck, will earn me 400, I need to spend 5 hours.
• Task Grace, will earn me 400, I need to spend 6 hours.

Is it possible to get a data structure which will have this result:

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

Explanation:

Note: I can't retake a task once it is done.

As you can see with tasks Franck and Grace, which both earn 400, for respectively 5 hours of work and 6 hours of work. 400 | 5 comes first, because if I could only do one job out of the two (earn 400) I would chose task F, since it will take me less to earn the same.

Now between task David 1000 | 20 and Elsa, 1200 | 60, even if task D earn technically 50 per hour, and task E only earn 20 per hour, I would still chose task E 1200 | 60, because if I could take only one job out of the two, I will chose to earn 1200 instead of 1000.

My question: what is the best data structure in Java to represent this please?

I've tried:

• HashMap:

Unfortunately, HashMap isn't sorted, and in order to decide which jobs to take, I need to build one for loop to find the maximum, and if I find multiple, to loop again on the values to get the minimum.

• Two PriorityQueues.

While one queue will order properly the earning, and one will order properly the hours, I will end up with

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

I lose all relationship and "mapping" between the two, making searches ineffective.

What would be the best way to find a Task with the max reward and the min of amount of time (for tasks with equal rewards)?

P.S. From the comments, it seems this looks like a leetcode question or homework, but it is not, I am just trying to find what is the best data structure to tackle this problem.

Solution

Use the Power of Objects

Firstly, you need an object Task, attempts to maintain values of rewards and hours separately are error-prone not viable.

Irregardless of this particular problem, it's not justifiable to store separately values which make sense only as a whole. They should constitute an object.

Hence, you need to create a class, or a Java 16 record. I'll go with the latter, because this option far is more concise.

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

Choosing a Data structure

Now, let's get back to the actual problem.

We need a data structure which would allow to consume these tasks in sorted order. For that purpose, we can use either a Red-black tree (represented with a TreeSet class in the JDK), or a Heap (represented with a PriorityQueue class in the JDK).

From the performance perspective, maintaining a Heap is less constful than maintaining a Red-black tree.

And using a Heap also fits very well in the nature of tasks. Once a task is consumed it can't be useful anymore, hence there's no need to store it. And with a Max-Heap (a Heap where all elements are lower or equal to the root-element) to access the maximum element we need to have a look at its root. And in order to find the next maximum element we need to remove the current root.

Hence, PriorityQueue would be an optimal choice.

Implementation

While instantiating PriorityQueue to make it capable to dial with our objects, they either need to implement Comparable interface, or we need to provide a Comparator.

I'll go with the second option because I don't feel Task has a natural order (the only sorted order which make sense for the object), because we might want to sort them differently.

Since Java 8 the recommended way to implement a Comparator is by using static methods of this interface. Each of these methods like comparing() and comparingInt() returns a Comparator and we can chain them in a fluent way in order to create a comparator based on the multiple conditions.

Here's how it can be implemented using PriorityQueue:

Queue<Task> tasks = new PriorityQueue<>(
    Comparator.comparingInt(Task::reward)
        .thenComparing(Task::hours, Comparator.reverseOrder())
        .reversed()
);
        
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);
}

Output:

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]

Answered By - Alexander Ivanchenko
Answer Checked By - Robin (JavaFixing Admin)