LeetCode Solutions Blog

Design Task Manager

Number: 3678

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

The task is to design a task management system that supports adding tasks, modifying their priority, removing tasks, and executing the highest priority task. Each task is associated with a user. When executing, if multiple tasks share the highest priority, the task with the highest taskId should be executed and removed from the system.

Key Insights

Use a hash map (dictionary) to map each taskId to its corresponding userId and priority.
Use a max-heap (priority queue) to efficiently extract the task with the highest priority and, in case of a tie, the highest taskId.
Handle updates (edit and remove) by marking obsolete entries. Lazy deletion from the heap is necessary, as direct random-access update is non-trivial in heap structures.
Each operation should work in logarithmic time relative to the number of tasks.

Space and Time Complexity

Time Complexity:

add: O(log n) due to heap insertion
edit: O(log n) for re-insertion in the heap (lazy deletion of old value)
rmv: O(1) for deletion from the hash map, O(log n) amortized during execTop due to lazy removal
execTop: O(log n) average per removal (may require several heap pops if encountering stale entries)

Space Complexity:

O(n) for storing tasks in both the hash map and the heap.

Solution

We maintain two main data structures:

Hash Map (e.g., map): This maps each taskId to a tuple (userId, priority). It allows constant time lookups for modifications and removals.
Max-Heap (priority queue): Each entry is a tuple (priority, taskId) where higher priority and higher taskId make an element come out first. Since Python's heap is a min-heap by default, we store negative priority and negative taskId values. In languages like C++ or Java, use custom comparators.

For update operations (edit and remove), instead of directly updating the heap, we update the hash map and add new entries to the heap (when editing). During execution (execTop), we pop from the heap until we find an entry that matches the current values in the hash map (i.e., not stale) or the heap is empty.

Code Solutions

# Python implementation
import heapq

class TaskManager:
    def __init__(self, tasks):
        # mapping taskId -> (userId, priority)
        self.task_map = {}
        # max-heap maintained as a min-heap with negative values to simulate max behavior.
        self.heap = []
        
        # Initialize with provided tasks: [userId, taskId, priority]
        for userId, taskId, priority in tasks:
            self.task_map[taskId] = (userId, priority)
            # Push tuple of (-priority, -taskId, taskId)
            heapq.heappush(self.heap, (-priority, -taskId, taskId))

    def add(self, userId, taskId, priority):
        # Add new task and push to heap.
        self.task_map[taskId] = (userId, priority)
        heapq.heappush(self.heap, (-priority, -taskId, taskId))

    def edit(self, taskId, newPriority):
        # Update the task's priority in the map.
        if taskId in self.task_map:
            userId, _ = self.task_map[taskId]
            self.task_map[taskId] = (userId, newPriority)
            # Push update to heap.
            heapq.heappush(self.heap, (-newPriority, -taskId, taskId))

    def rmv(self, taskId):
        # Remove task by deleting from map.
        if taskId in self.task_map:
            del self.task_map[taskId]

    def execTop(self):
        # Execute the valid max task.
        while self.heap:
            # Peek and pop from heap.
            neg_priority, neg_taskId, taskId = heapq.heappop(self.heap)
            # Check if taskId is still in map and its priority matches.
            if taskId in self.task_map:
                userId, current_priority = self.task_map[taskId]
                # Ensure the entry from heap is current.
                if current_priority == -neg_priority:
                    # Valid task, remove it.
                    del self.task_map[taskId]
                    return userId
                # Else, stale entry, continue.
        # No valid tasks to execute.
        return -1

# Example usage:
# tm = TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]])
# tm.add(4, 104, 5)
# tm.edit(102, 8)
# print(tm.execTop())  # returns 3
# tm.rmv(101)
# tm.add(5, 105, 15)
# print(tm.execTop())  # returns 5