LeetCode Problem 3408

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set

Solution

LeetCode 3408. Design Task Manager

Problem Understanding

This problem asks us to design a data structure that maintains a collection of tasks belonging to different users.

Each task has three pieces of information:

• userId, the user who owns the task
• taskId, a unique identifier for the task
• priority, which determines execution order

The system must support four operations:

• add: insert a new task
• edit: change the priority of an existing task
• rmv: remove an existing task
• execTop: find and execute the task with the highest priority

The execution rule is important:

• Higher priority always wins.
• If two tasks have the same priority, the larger taskId wins.
• After execution, the task is removed from the system.
• The method returns the corresponding userId.
• If no tasks exist, return -1.

The input constructor receives an initial list of tasks, where each entry is:

[userId, taskId, priority]

The constraints are large:

• Up to 10^5 initial tasks.
• Up to 2 * 10^5 additional operations.
• Priorities can be as large as 10^9.

These constraints immediately rule out repeatedly scanning all tasks whenever execTop() is called. A linear search could become far too expensive.

The problem guarantees:

• Every taskId is unique when added.
• Every edit() and rmv() call references an existing task.
• A user may own multiple tasks.

Important edge cases include an empty system, multiple tasks sharing the same priority, repeated edits of the same task, and removals occurring before outdated heap entries are processed.

Approaches

Brute Force

A straightforward solution stores every task in a hash table:

taskId -> (userId, priority)

When execTop() is called, scan every active task and find the one with:

1. Maximum priority.
2. Maximum taskId among ties.

After finding the best task, remove it and return its user.

This is correct because every execution explicitly checks all active tasks and therefore always finds the proper maximum.

However, the time complexity is too high. If there are N active tasks, every execTop() requires O(N) work. With up to hundreds of thousands of operations, this becomes impractical.

Optimal Approach

The key observation is that execTop() repeatedly asks for the maximum task according to:

(priority, taskId)

This is exactly the type of query that a priority queue handles efficiently.

A max-heap allows us to retrieve the highest-priority task in logarithmic time.

The challenge is that heaps do not support efficient arbitrary deletion or priority updates.

The standard solution is lazy deletion:

• Keep the authoritative task information in a hash map.
• Every add or edit pushes a new heap entry.
• Removed or outdated entries remain inside the heap temporarily.
• Whenever we access the heap top, we verify that the entry still matches the current task information.
• Invalid entries are discarded until a valid one is found.

This technique allows all operations to remain efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N) per execTop()	O(N)	Scan all active tasks every time
Optimal	O(log N) per operation	O(N)	Hash map + heap with lazy deletion

Algorithm Walkthrough

1. Create a hash map:

taskInfo[taskId] = (userId, priority)

This map always stores the current valid state of every active task. 2. Create a max-heap ordered by:

priority descending
taskId descending

Since Python's heapq is a min-heap, store:

(-priority, -taskId)

3. During initialization, insert every task into both the hash map and the heap.
4. For add(userId, taskId, priority):

• Insert into the hash map.
• Push a new heap entry.

5. For edit(taskId, newPriority):

• Read the current user from the hash map.
• Update the hash map entry.
• Push a new heap entry with the new priority.

The old heap entry is left in the heap. 6. For rmv(taskId):

• Remove the task from the hash map.

Any heap entries referring to this task automatically become invalid. 7. For execTop():

• Repeatedly inspect the heap top.

• Extract the candidate entry.

• Check whether the task still exists in the hash map.

• Check whether its priority matches the current priority.

• If either check fails, discard the heap entry and continue.

• Once a valid entry is found:

• Remove the task from the hash map.

• Return its userId.

8. If the heap becomes empty, return -1.

Why it works

The hash map always contains the current valid version of every active task. Every modification creates a new heap entry, while outdated entries remain in the heap. During execution, lazy deletion removes any entry whose information no longer matches the hash map. Therefore, the first valid heap entry encountered is guaranteed to be the active task with maximum (priority, taskId), exactly matching the problem's ordering rule.

Python Solution

from typing import List
import heapq

class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.tasks = {}  # taskId -> (userId, priority)
        self.heap = []

        for user_id, task_id, priority in tasks:
            self.tasks[task_id] = (user_id, priority)
            heapq.heappush(self.heap, (-priority, -task_id))

    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.tasks[taskId] = (userId, priority)
        heapq.heappush(self.heap, (-priority, -taskId))

    def edit(self, taskId: int, newPriority: int) -> None:
        user_id, _ = self.tasks[taskId]
        self.tasks[taskId] = (user_id, newPriority)
        heapq.heappush(self.heap, (-newPriority, -taskId))

    def rmv(self, taskId: int) -> None:
        del self.tasks[taskId]

    def execTop(self) -> int:
        while self.heap:
            neg_priority, neg_task_id = heapq.heappop(self.heap)

            priority = -neg_priority
            task_id = -neg_task_id

            if task_id not in self.tasks:
                continue

            user_id, current_priority = self.tasks[task_id]

            if current_priority != priority:
                continue

            del self.tasks[task_id]
            return user_id

        return -1

The implementation uses two data structures.

The hash map self.tasks stores the authoritative state of every active task. Any edit immediately updates this map, and any removal deletes the corresponding entry.

The heap stores candidate tasks ordered by priority and task ID. Every add and edit pushes a new heap record. Because old versions are not removed immediately, the heap may contain stale entries.

The execTop() method performs lazy deletion. It repeatedly removes heap entries until it finds one whose priority exactly matches the current value stored in the hash map. At that moment the entry represents the highest valid task and can safely be executed.

Go Solution

package main

import "container/heap"

type Entry struct {
	priority int
	taskId   int
}

type MaxHeap []Entry

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	if h[i].priority != h[j].priority {
		return h[i].priority > h[j].priority
	}
	return h[i].taskId > h[j].taskId
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Entry))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type TaskData struct {
	userId   int
	priority int
}

type TaskManager struct {
	tasks map[int]TaskData
	h     MaxHeap
}

func Constructor(tasks [][]int) TaskManager {
	tm := TaskManager{
		tasks: make(map[int]TaskData),
		h:     MaxHeap{},
	}

	heap.Init(&tm.h)

	for _, task := range tasks {
		userId := task[0]
		taskId := task[1]
		priority := task[2]

		tm.tasks[taskId] = TaskData{
			userId:   userId,
			priority: priority,
		}

		heap.Push(&tm.h, Entry{
			priority: priority,
			taskId:   taskId,
		})
	}

	return tm
}

func (this *TaskManager) Add(userId int, taskId int, priority int) {
	this.tasks[taskId] = TaskData{
		userId:   userId,
		priority: priority,
	}

	heap.Push(&this.h, Entry{
		priority: priority,
		taskId:   taskId,
	})
}

func (this *TaskManager) Edit(taskId int, newPriority int) {
	data := this.tasks[taskId]

	this.tasks[taskId] = TaskData{
		userId:   data.userId,
		priority: newPriority,
	}

	heap.Push(&this.h, Entry{
		priority: newPriority,
		taskId:   taskId,
	})
}

func (this *TaskManager) Rmv(taskId int) {
	delete(this.tasks, taskId)
}

func (this *TaskManager) ExecTop() int {
	for this.h.Len() > 0 {
		top := heap.Pop(&this.h).(Entry)

		data, exists := this.tasks[top.taskId]
		if !exists {
			continue
		}

		if data.priority != top.priority {
			continue
		}

		delete(this.tasks, top.taskId)
		return data.userId
	}

	return -1
}

The Go implementation follows exactly the same strategy as the Python version. The primary difference is that Go uses the container/heap package and requires a custom heap type implementing the heap interface. The heap is defined as a max-heap through the Less() function. Since priorities are at most 10^9, the standard Go int type is sufficient on LeetCode platforms.

Worked Examples

Example 1

Initial tasks:

Task	User	Priority
101	1	10
102	2	20
103	3	15

Current map:

taskId	(userId, priority)
101	(1, 10)
102	(2, 20)
103	(3, 15)

After:

add(4, 104, 5)

taskId	(userId, priority)
101	(1, 10)
102	(2, 20)
103	(3, 15)
104	(4, 5)

After:

edit(102, 8)

Map:

taskId	(userId, priority)
101	(1, 10)
102	(2, 8)
103	(3, 15)
104	(4, 5)

Heap now contains both versions of task 102:

(20,102)  stale
(8,102)   current

Call:

execTop()

Heap top is (20,102).

Map says task 102 currently has priority 8.

Therefore this heap entry is stale and discarded.

Next heap top:

(15,103)

This matches the map.

Task 103 is executed and removed.

Return:

3

Current active tasks:

taskId	(userId, priority)
101	(1, 10)
102	(2, 8)
104	(4, 5)

Call:

rmv(101)

Map:

taskId	(userId, priority)
102	(2, 8)
104	(4, 5)

Call:

add(5, 105, 15)

Map:

taskId	(userId, priority)
102	(2, 8)
104	(4, 5)
105	(5, 15)

Call:

execTop()

Highest valid task:

(15,105)

Execute task 105.

Return:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log N) amortized per operation	Heap insertion and removal are logarithmic
Space	O(N + M)	Active tasks plus stale heap entries created by updates

Let N be the number of active tasks and M be the total number of operations.

Each add or edit inserts one heap entry. Although stale entries accumulate, every stale entry is removed from the heap at most once. Therefore the total work spent discarding stale entries is bounded by the total number of heap insertions, giving amortized O(log N) performance per operation.

Test Cases

# Example from statement
tm = TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]])
tm.add(4, 104, 5)
tm.edit(102, 8)
assert tm.execTop() == 3  # stale heap entry ignored
tm.rmv(101)
tm.add(5, 105, 15)
assert tm.execTop() == 5  # highest priority task

# Single task
tm = TaskManager([[7, 1, 100]])
assert tm.execTop() == 7  # execute only task
assert tm.execTop() == -1  # empty structure

# Tie on priority, larger taskId wins
tm = TaskManager([
    [1, 10, 50],
    [2, 20, 50]
])
assert tm.execTop() == 2  # taskId 20 wins tie
assert tm.execTop() == 1

# Edit increases priority
tm = TaskManager([[1, 1, 5], [2, 2, 10]])
tm.edit(1, 20)
assert tm.execTop() == 1  # edited task becomes top

# Edit decreases priority
tm = TaskManager([[1, 1, 20], [2, 2, 10]])
tm.edit(1, 1)
assert tm.execTop() == 2  # other task now wins

# Removal before execution
tm = TaskManager([[1, 1, 100]])
tm.rmv(1)
assert tm.execTop() == -1  # removed task ignored

# Multiple edits creating many stale entries
tm = TaskManager([[1, 1, 10]])
tm.edit(1, 20)
tm.edit(1, 30)
tm.edit(1, 40)
assert tm.execTop() == 1  # newest version survives
assert tm.execTop() == -1

# Priority zero values
tm = TaskManager([[1, 1, 0], [2, 2, 0]])
assert tm.execTop() == 2  # larger taskId wins
assert tm.execTop() == 1

# Large priority values
tm = TaskManager([
    [1, 1, 10**9],
    [2, 2, 10**9 - 1]
])
assert tm.execTop() == 1  # handles maximum priority

Test Summary

Test	Why
Provided example	Verifies full workflow
Single task	Smallest meaningful case
Equal priorities	Validates tie-breaking by taskId
Priority increase	Ensures edits update ordering
Priority decrease	Ensures edited task can lose top position
Removal before execution	Verifies lazy deletion correctness
Multiple edits	Tests accumulation of stale heap entries
Zero priorities	Checks lower boundary values
Large priorities	Checks upper boundary values

Edge Cases

Empty System During Execution

After enough removals or executions, the system may contain no active tasks. A naive implementation could attempt to access the heap top and fail. The implementation continuously removes invalid heap entries and returns -1 once the heap becomes empty.

Multiple Tasks With Equal Priority

The problem specifies a secondary ordering rule: when priorities are equal, the larger taskId must be executed first. Forgetting this tie-breaker produces incorrect answers. The heap ordering explicitly compares taskId whenever priorities are equal, guaranteeing the correct task is selected.

Repeated Priority Updates

A task may be edited many times before execution. Since heaps do not efficiently support updating existing entries, old versions remain inside the heap. Without validation, an outdated priority could be executed. The implementation stores the latest priority in the hash map and verifies every heap entry against that authoritative record before execution.

Removed Tasks Still Present in the Heap

A removed task may still have one or more entries sitting inside the heap. If those entries are not checked, a deleted task could accidentally be executed later. The implementation first checks whether the task still exists in the hash map. If not, the heap entry is discarded immediately.

Large Numbers of Operations

With up to 3 * 10^5 total tasks and operations, any solution involving linear scans becomes too slow. The heap plus lazy deletion approach guarantees logarithmic updates and amortized logarithmic execution, which comfortably satisfies the constraints.