Design Task Manager

• Data Structure: Use a HashMap<Integer, int[]> where the key is taskId and the value is an array [userId, priority].
• Initialization: In the constructor, iterate through the initial list of tasks and populate the HashMap.
• add(userId, taskId, priority): Insert a new entry into the HashMap. This is an O(1) operation.
• edit(taskId, newPriority): Access the task by its taskId in the HashMap and update its priority value. This is an O(1) operation.
• rmv(taskId): Remove the entry corresponding to taskId from the HashMap. This is an O(1) operation.
• execTop():
  • If the map is empty, return -1.
  • Initialize variables to track the best task found so far (e.g., maxPriority, bestTaskId, bestUserId).
  • Iterate through every task in the HashMap.
  • For each task, compare its priority (and taskId for tie-breaking) with the current best task.
  • If the current task is better, update the tracking variables.
  • After checking all tasks, the best task has been identified. Remove it from the HashMap and return its userId.

Data Structure

The core of this approach is a java.util.HashMap that maps each taskId to an integer array containing its userId and priority. This provides O(1) average-case time complexity for lookups, insertions, and deletions by taskId.

Method Implementations

• add, edit, rmv: These methods directly translate to the HashMap's put, get/put, and remove operations, respectively. Since taskId is guaranteed to exist for edit and rmv, these operations are straightforward and efficient.
• execTop: This is the performance bottleneck. To find the highest priority task, we have no choice but to perform a full linear scan of all the values in the HashMap. We iterate through each task, keeping track of the one with the highest priority seen so far. If two tasks have the same priority, the one with the larger taskId is chosen. Once the entire map has been traversed, the winning task is removed from the map, and its userId is returned.

1import java.util.HashMap;2import java.util.Map;3 4class TaskManager {5    private Map<Integer, int[]> taskMap; // taskId -> {userId, priority}6 7    public TaskManager(int[][] tasks) {8        taskMap = new HashMap<>();9        for (int[] task : tasks) {10            add(task[0], task[1], task[2]);11        }12    }13 14    public void add(int userId, int taskId, int priority) {15        taskMap.put(taskId, new int[]{userId, priority});16    }17 18    public void edit(int taskId, int newPriority) {19        // The problem guarantees taskId exists.20        taskMap.get(taskId)[1] = newPriority;21    }22 23    public void rmv(int taskId) {24        taskMap.remove(taskId);25    }26 27    public int execTop() {28        if (taskMap.isEmpty()) {29            return -1;30        }31 32        int bestTaskId = -1;33        int maxPriority = -1;34        int bestUserId = -1;35 36        for (Map.Entry<Integer, int[]> entry : taskMap.entrySet()) {37            int currentTaskId = entry.getKey();38            int[] taskDetails = entry.getValue();39            int currentPriority = taskDetails[1];40 41            if (currentPriority > maxPriority) {42                maxPriority = currentPriority;43                bestTaskId = currentTaskId;44                bestUserId = taskDetails[0];45            } else if (currentPriority == maxPriority) {46                if (currentTaskId > bestTaskId) {47                    bestTaskId = currentTaskId;48                    bestUserId = taskDetails[0];49                }50            }51        }52 53        taskMap.remove(bestTaskId);54        return bestUserId;55    }56}

• Data Structures:
  • A PriorityQueue<int[]> (Max-Heap) to store tasks as [priority, taskId, userId]. It's ordered by priority, then taskId, to make finding the top task efficient.
  • A HashMap<Integer, int[]> to map taskId to [userId, priority]. This map serves as the single source of truth for a task's current state.
• add(userId, taskId, priority): Add the task to both the HashMap and the PriorityQueue.
• edit(taskId, newPriority): Update the task's priority in the HashMap. Then, add a new entry for this task with the updated priority to the PriorityQueue. The old entry in the queue is not removed; it becomes 'stale'.
• rmv(taskId): Remove the task from the HashMap. The corresponding entry in the PriorityQueue becomes 'stale'.
• execTop():
  • Repeatedly look at the top element of the PriorityQueue.
  • Check if this task is 'stale' by comparing it with the information in the HashMap. A task is stale if it's not in the map, or if its priority in the queue doesn't match the current priority in the map.
  • If the top task is stale, remove it from the queue and repeat.
  • If the top task is valid, it's the one to be executed. Remove it from both the queue and the map, and return its userId.

Data Structures and Strategy

We use two main data structures:

1. PriorityQueue<int[]>: A max-heap that stores task information as [priority, taskId, userId]. The custom comparator ensures that elements with higher priority are at the top. For ties in priority, the element with the higher taskId takes precedence. This makes finding the best task an O(log M) operation.
2. HashMap<Integer, int[]>: This map stores the ground truth for each task, mapping a taskId to its [userId, priority]. It allows for O(1) updates and lookups.

The key idea is lazy deletion. When a task is edited or removed, we don't try to find and remove the old entry from the heap (which is an O(M) operation). Instead, we mark it as invalid by either updating (edit) or removing (rmv) its entry in the HashMap. The execTop method is then responsible for filtering out these 'stale' tasks from the top of the heap before executing a valid one.

Method Implementations

• add: A new task is added to both the HashMap and the PriorityQueue.
• edit: The task's priority is updated in the HashMap. A new entry representing the updated task is added to the PriorityQueue. The old entry is now stale.
• rmv: The task is removed from the HashMap. Its entry in the PriorityQueue is now stale.
• execTop: We peek at the top of the PriorityQueue. We check its validity against the HashMap. If the task doesn't exist in the map or its priority is outdated, we poll it and check the next one. This continues until a valid task is found at the top. This valid task is then removed from both data structures, and its userId is returned.

1import java.util.HashMap;2import java.util.Map;3import java.util.PriorityQueue;4 5class TaskManager {6    // Max-heap to get the top task efficiently. Stores {priority, taskId, userId}7    private PriorityQueue<int[]> pq;8    // Map to store the current valid state of a task. taskId -> {userId, priority}9    private Map<Integer, int[]> taskMap;10 11    public TaskManager(int[][] tasks) {12        // Comparator for the max-heap:13        // 1. Higher priority first.14        // 2. If priorities are equal, higher taskId first.15        pq = new PriorityQueue<>((a, b) -> {16            if (a[0] != b[0]) {17                return b[0] - a[0]; // Descending priority18            }19            return b[1] - a[1]; // Descending taskId20        });21 22        taskMap = new HashMap<>();23        for (int[] task : tasks) {24            add(task[0], task[1], task[2]);25        }26    }27 28    public void add(int userId, int taskId, int priority) {29        taskMap.put(taskId, new int[]{userId, priority});30        pq.offer(new int[]{priority, taskId, userId});31    }32 33    public void edit(int taskId, int newPriority) {34        int[] taskDetails = taskMap.get(taskId);35        taskDetails[1] = newPriority;36        // No need for taskMap.put() as the array is modified by reference37        38        // Add the new version of the task to the priority queue.39        // The old version is now "stale" and will be ignored by execTop.40        pq.offer(new int[]{newPriority, taskId, taskDetails[0]});41    }42 43    public void rmv(int taskId) {44        // Simply remove from the map. The entry in the PQ becomes "stale".45        taskMap.remove(taskId);46    }47 48    public int execTop() {49        // Clean up stale tasks from the top of the queue50        while (!pq.isEmpty()) {51            int[] topTask = pq.peek();52            int priority = topTask[0];53            int taskId = topTask[1];54 55            // A task is valid if it exists in the map and its priority matches.56            if (taskMap.containsKey(taskId) && taskMap.get(taskId)[1] == priority) {57                // Valid task found, execute it58                pq.poll(); // Remove from pq59                taskMap.remove(taskId); // Remove from map60                return topTask[2]; // Return userId61            } else {62                // This is a stale task (either removed or edited), discard it.63                pq.poll();64            }65        }66        // No valid tasks left67        return -1;68    }69}