Find largest value smallest value and value of largest key in Data Structure

Question

I have a system that stores a huge number of tasks. Each task has the following parameters:

Time t       
Priority p      

Every task has a unique time. That means no 2 tasks can have the same Time parameter.
However, Priority is not unique. Multiple tasks can have the same priorities.

I need to design a system which can address four types of queries. The probability of each type of query is equally likely. Following are the types of queries:

1. UpdateTask(t,p)
   This query wants the system to set the priority of task at time t to priority p. If the task does not exist in the system, a fresh task is created. If the task is present, its priority is updated.

2. DeleteTask(t)
   This query wants the system to delete a task that is associated with time t. If such a task is not present in the system, then no action needs to be taken.

3. GetMaximumPriority() and GetMinimumPriority()
   This query wants the system to print the minimum priority and maximum priority of the tasks available in the system.

4. GetPriorityofTaskAtMaximumTime()
   This query wants the system to print the priority of the task that has the maximum value of parameter t (time)

I need to design the data structure for this system and implement algorithms for those data structures. I need to implement this in Java.

My approach: Created a HashMap with Key as Time and Value as Priority. The HashMap allows me to address the first two queries in constant time. But the last two queries have a time complexity of O(n).

Question: Is there a better time efficient and space efficient data structures and algorithms for this problem? I mainly need an approach to solve this. Fully implemented code is not necessary. Thanks.

Answer 1

One possible way is to maintain two indices: one for the time, and one for the priority. Let's take two balanced search trees with a constant time firstKey() / lastKey() operations. I will use the interface of the TreeMap, but it should have an implementation similar to std::map from c++ (it just maintains the iterators to the first and last elements during updates).

First map would be Map<Time, Priority> tasks , second - Map<Priority, Integer> priorities. The second map for every existing priority value stores the number of tasks with this priority value. Thus, you can use tasks for the fourth query, and priorities for the third query.

1. UpdateTask(t, p)

   Priority oldp = tasks.put(t, p);
   if (oldp != null) {
       decreasePriority(oldp);     
   } 
   increasePriority(p);
   

   Complexity: O(log(n))
   
   

2. DeleteTask(t)

   if (tasks.containsKey(t)) {
       Priority oldp = tasks.get(t);
       tasks.remove(t);
       decreasePriority(oldp); 
   }
   

   Complexity: O(log(n))
   
   

3. GetMaximumPriority(), GetMinimumPriority()

   return priorities.lastKey();
   
   return priorities.firstKey();     
   

   Complexity: O(1) (with proper lastKey()/firstKey() implementation, O(log(n)) with a java.util.TreeMap).
   
   

4. GetPriorityofTaskAtMaximumTime()

   return tasks.lastEntry().getValue();
   

   Complexity: O(1) (with proper lastEntry() implementation, O(log(n)) with a java.util.TreeMap)

---

    void increasePriority(p) {
        if (priorities.hasKey(p)) { 
            priorities.put(p, priorities.get(p) + 1);
        } else {
            priorities.put(p, 1); 
        }    
    }

    void decreasePriority(p) {
        int count = priorities.get(p);
        if (count > 1) {  
            priorities.put(p, count - 1);
        } else {
            priorities.remove(p);
        }   
    }

As a result, you will avoid linear complexities in operations.