Skip to content

3408.design-task-manager.md

Latest commit

 

History

History
291 lines (238 loc) · 8.76 KB

3408.design-task-manager.md

File metadata and controls

291 lines (238 loc) · 8.76 KB

3408. Design Task Manager

Heap + Hash Map

We can maintain a heap of tasks to find the highest priority task and a hash map of tasks to find the task by id.

data class Task(
    val userId: Int,
    val taskId: Int,
    val priority: Int
)

class TaskManager(tasks: List<List<Int>>) {
    
    init {
        for (task in tasks) {
            add(task[0], task[1], task[2])
        }
    }

    val taskMap = HashMap<Int, Task>()
    val taskHeap = PriorityQueue<Task>(compareByDescending<Task> { it.priority }.thenByDescending { it.taskId })

    fun add(userId: Int, taskId: Int, priority: Int) {
        val newTask = Task(userId, taskId, priority)
        taskMap[taskId] = newTask
        taskHeap.add(newTask)
    }

    fun edit(taskId: Int, newPriority: Int) {
        val task = taskMap[taskId] ?: return
        val updatedTask = task.copy(priority = newPriority)
        taskMap[taskId] = updatedTask
    }

    fun rmv(taskId: Int) {
        taskMap.remove(taskId)
    }

    fun execTop(): Int { // return user id or -1 (no task)
        if (taskHeap.isEmpty()) return -1
        val executedTask = taskHeap.poll()
        taskMap.remove(executedTask.taskId)
        return executedTask.userId
    }
}

But the implementation is not fully correct, because the heap is not updated when the priority is updated or the task is removed. This causes stale tasks in the heap. Let's take a look at the following example:

Initial task: {A: 10, B: 20}
// heap:
A: 10 
B: 20

edit(A, 30) {A: 30, B: 20}
A: 10 (stale: priority updated)
B: 20

remove(B): {A: 30}
A: 10 (stale: priority updated)
B: 20

execute()

We have updated the priority of A to 30, but the heap is not updated. So when we execute the task, it will return B: 20 instead of A: 30.

Or we remove B, but the heap is not updated. So when we execute the task, it will return B: 20 instead of A: 10.

Initial task: {A: 10, B: 20}
A: 10 
B: 20

remove(B): {A: 10}
A: 10 
B: 20 (stale: removed)

execute()

Potential Solutions

Option 1: Lazy Deletion

We don't modify or remove the stale tasks in the heap when it's edited or removed. Instead, we:

  • Use taskMap as the source of truth for the task.
  • We push a new version of the task to the heap when the priority is updated. (Heap has multiple versions of the same task, but only the latest version exists in taskMap)
  • When execTop() is called, we skip the stale tasks in the heap. (i.e. tasks are removed or priority is updated)
Function Behavior
add() Insert task to both taskMap and heap.
edit() Update taskMap, then add new version to heap.
rmv() Remove from taskMap, but not heap.
execTop() Pop from heap until a valid (non-stale) task is found.

One edge case: We can remove the task, then reuse the same task id with a new user.

add(A, user1, 10)
remove(A)
add(A, user2, 20)

// heap:
A: 10 (stale)
A: 20
class TaskManager(tasks: List<List<Int>>) {

    val taskMap = HashMap<Int, Task>()
    val taskHeap = PriorityQueue<Task>(compareByDescending<Task> { it.priority }.thenByDescending { it.taskId })

    init {
        for (task in tasks) {
            add(task[0], task[1], task[2])
        }
    }

    fun add(userId: Int, taskId: Int, priority: Int) {
        val newTask = Task(userId, taskId, priority)
        taskMap[taskId] = newTask
        taskHeap.add(newTask) // Push new task to heap
    }

    fun edit(taskId: Int, newPriority: Int) {
        val task = taskMap[taskId] ?: return
        val updatedTask = task.copy(priority = newPriority)
        taskMap[taskId] = updatedTask
        taskHeap.add(updatedTask) // Push updated versio to heap
    }

    fun rmv(taskId: Int) {
        taskMap.remove(taskId)
        // Don't remove from heap, we will skip the stale tasks in `execTop()`
    }

    fun execTop(): Int {
        while (taskHeap.isNotEmpty()) {
            val top = taskHeap.poll()
            val mapping = taskMap[top.taskId]
            // Is this the latest version of the task and still exists?
            // We need a strict equality check here, because the task id is reused.
            if (mapping != null && top == mapping) {
                taskMap.remove(top.taskId)
                return top.userId
            }
            // Else: stale task (priority updated or removed), skip it
        }
        return -1
    }
}
  • Time Complexity: O(log n) for add(), edit(), rmv(), execTop() for single operation
  • Space Complexity: O(n) for taskMap and taskHeap

Option 2: Versioning

  • Each Task has a version number that is incremented on every add() or edit().
  • The heap may contain multiple versions of the same task.
  • taskMap always stores the latest version.
  • In execTop(), we compare top.version == taskMap[taskId]?.version to ensure we only execute the current version. (i.e. the latest version)
  • Old (stale) versions are ignored when popped.
data class Task(
    ...
    val version: Int
)

class TaskManager(tasks: List<List<Int>>) {

    private val taskMap = HashMap<Int, Task>()   // taskId -> latest Task
    private val taskHeap = PriorityQueue<Task>(
        compareByDescending<Task> { it.priority }
            .thenByDescending { it.taskId }
            .thenByDescending { it.version }  // ensure most recent wins
    )
    private var versionCounter = 0

    init {
        for (task in tasks) {
            add(task[0], task[1], task[2])
        }
    }

    fun add(userId: Int, taskId: Int, priority: Int) {
        val task = Task(userId, taskId, priority, versionCounter++)
        taskMap[taskId] = task
        taskHeap.add(task)
    }

    fun edit(taskId: Int, newPriority: Int) {
        val oldTask = taskMap[taskId] ?: return
        val newTask = oldTask.copy(priority = newPriority, version = versionCounter++)
        taskMap[taskId] = newTask
        taskHeap.add(newTask)
    }

    fun rmv(taskId: Int) {
        taskMap.remove(taskId)
        // stale versions remain in heap, but will be ignored
    }

    fun execTop(): Int {
        while (taskHeap.isNotEmpty()) {
            val top = taskHeap.poll()
            val current = taskMap[top.taskId]
            // Here we compare the version
            if (current != null && current.version == top.version) {
                taskMap.remove(top.taskId)
                return top.userId
            }
        }
        return -1
    }
}

Option 3: Rebuild Heap (Not Recommended)

We rebuild the heap every time when the priority is updated or the task is removed. This is a simple straightforward solution, but it's costly and not efficient.

// When the priority is updated or the task is removed
taskHeap.clear()
taskHeap.addAll(taskMap.values)

Tree Map (Set) + Hash Map

  • HashMap is used to quick lookup from task ID to the task: (taskId to Task)
  • TreeMap is used to maintain the priority of tasks: (Task to priority)
class TaskManager(tasks: List<List<Int>>) {

    private val taskMap = HashMap<Int, Task>()    // taskId -> latest Task for user id quick lookup
    private val priorityMap = TreeMap<Task, Int>( // task to its taskId
        compareByDescending<Task> { it.priority }
            .thenByDescending { it.taskId }
    )
    
    init {
        for (task in tasks) {
            add(task[0], task[1], task[2])
        }
    }

    fun add(userId: Int, taskId: Int, priority: Int) {
        val task = Task(userId, taskId, priority)
        taskMap[taskId] = task
        priorityMap[task] = taskId
    }

    fun edit(taskId: Int, newPriority: Int) {
        val oldTask = taskMap[taskId] ?: return
        // Remember to remove the old task from the priority map first
        priorityMap.remove(oldTask)
        val updatedTask = oldTask.copy(priority = newPriority)
        taskMap[taskId] = updatedTask
        // Then add the new task to the priority map
        priorityMap[updatedTask] = newPriority
    }

    fun rmv(taskId: Int) {
        val task = taskMap[taskId] ?: return
        taskMap.remove(taskId)
        priorityMap.remove(task)
    }

    fun execTop(): Int {
        if (priorityMap.isEmpty()) return -1
        val task = priorityMap.firstKey()
        priorityMap.remove(task)
        taskMap.remove(task.taskId)
        return task.userId
    }
}
  • Time Complexity:
    • add(): O(log n)
    • edit(): O(log n)
    • rmv(): O(log n)
    • execTop(): O(log n)
  • Space Complexity: O(n) for taskMap and priorityMap

This solution has several advantages:

  1. No need to handle stale tasks or versions
  2. Clean and straightforward implementation