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 spend10
hours. - Task Bob, will earn me
2000
, I need to spend3
hours. - Task Charlie, will earn me
100
, I need to spend1
hour. - Task David, will earn me
1000
, I need to spend20
hours. - Task Elsa, will earn me
1200
, I need to spend60
hours. - Task Franck, will earn me
400
, I need to spend5
hours. - Task Grace, will earn me
400
, I need to spend6
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
PriorityQueue
s.
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.
CodePudding user response:
Use the Power of Objects
Firstly, you need an object Task
, attempts to maintain values of rewards and hours separately are error-prone and 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) // 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);
}
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]