登录[Python3/Java/C++/Go/TypeScript] 一题一解：哈希表 + 有序集合（清晰题解）
方法一：哈希表 + 有序集合
我们用一个哈希表 $\text{d}$ 来存储任务信息，键为任务 ID，值为一个二元组 $(\text{userId}, \text{priority})$，表示该任务所属的用户 ID 以及任务的优先级。
我们用一个有序集合 $\text{st}$ 来存储当前系统中的所有任务，元素为一个二元组 $(-\text{priority}, -\text{taskId})$，表示任务的优先级和任务 ID 的相反数。我们将优先级和任务 ID 取相反数是为了让优先级最高且任务 ID 最大的任务在有序集合中排在最前面。
对于每个操作，我们可以按如下方式进行处理：
- 初始化：对于每个任务 $(\text{userId}, \text{taskId}, \text{priority})$，我们将其添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
- 添加任务：将任务 $(\text{userId}, \text{taskId}, \text{priority})$ 添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
- 编辑任务：从哈希表 $\text{d}$ 中获取任务 ID对应的用户 ID 和旧优先级，然后从有序集合 $\text{st}$ 中删除旧的任务信息，再将新的任务信息添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
- 删除任务：从哈希表 $\text{d}$ 中获取任务 ID 对应的优先级，然后从有序集合 $\text{st}$ 中删除任务信息，并从哈希表 $\text{d}$ 中删除任务。
- 执行最高优先级任务：如果有序集合 $\text{st}$ 为空，返回 -1。否则，从有序集合 $\text{st}$ 中取出第一个元素，获取任务 ID，然后从哈希表 $\text{d}$ 中获取对应的用户 ID，并将任务从哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中删除，最后返回用户 ID。
###python
class TaskManager:
def __init__(self, tasks: List[List[int]]):
self.d = {}
self.st = SortedList()
for task in tasks:
self.add(*task)
def add(self, userId: int, taskId: int, priority: int) -> None:
self.d[taskId] = (userId, priority)
self.st.add((-priority, -taskId))
def edit(self, taskId: int, newPriority: int) -> None:
userId, priority = self.d[taskId]
self.st.discard((-priority, -taskId))
self.d[taskId] = (userId, newPriority)
self.st.add((-newPriority, -taskId))
def rmv(self, taskId: int) -> None:
_, priority = self.d[taskId]
self.d.pop(taskId)
self.st.remove((-priority, -taskId))
def execTop(self) -> int:
if not self.st:
return -1
taskId = -self.st.pop(0)[1]
userId, _ = self.d[taskId]
self.d.pop(taskId)
return userId
# Your TaskManager object will be instantiated and called as such:
# obj = TaskManager(tasks)
# obj.add(userId,taskId,priority)
# obj.edit(taskId,newPriority)
# obj.rmv(taskId)
# param_4 = obj.execTop()
###java
class TaskManager {
private final Map<Integer, int[]> d = new HashMap<>();
private final TreeSet<int[]> st = new TreeSet<>((a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return b[0] - a[0];
});
public TaskManager(List<List<Integer>> tasks) {
for (var task : tasks) {
add(task.get(0), task.get(1), task.get(2));
}
}
public void add(int userId, int taskId, int priority) {
d.put(taskId, new int[] {userId, priority});
st.add(new int[] {priority, taskId});
}
public void edit(int taskId, int newPriority) {
var e = d.get(taskId);
int userId = e[0], priority = e[1];
st.remove(new int[] {priority, taskId});
st.add(new int[] {newPriority, taskId});
d.put(taskId, new int[] {userId, newPriority});
}
public void rmv(int taskId) {
var e = d.remove(taskId);
int priority = e[1];
st.remove(new int[] {priority, taskId});
}
public int execTop() {
if (st.isEmpty()) {
return -1;
}
var e = st.pollFirst();
var t = d.remove(e[1]);
return t[0];
}
}
/**
* Your TaskManager object will be instantiated and called as such:
* TaskManager obj = new TaskManager(tasks);
* obj.add(userId,taskId,priority);
* obj.edit(taskId,newPriority);
* obj.rmv(taskId);
* int param_4 = obj.execTop();
*/
###cpp
class TaskManager {
private:
unordered_map<int, pair<int, int>> d;
set<pair<int, int>> st;
public:
TaskManager(vector<vector<int>>& tasks) {
for (const auto& task : tasks) {
add(task[0], task[1], task[2]);
}
}
void add(int userId, int taskId, int priority) {
d[taskId] = {userId, priority};
st.insert({-priority, -taskId});
}
void edit(int taskId, int newPriority) {
auto [userId, priority] = d[taskId];
st.erase({-priority, -taskId});
st.insert({-newPriority, -taskId});
d[taskId] = {userId, newPriority};
}
void rmv(int taskId) {
auto [userId, priority] = d[taskId];
st.erase({-priority, -taskId});
d.erase(taskId);
}
int execTop() {
if (st.empty()) {
return -1;
}
auto e = *st.begin();
st.erase(st.begin());
int taskId = -e.second;
int userId = d[taskId].first;
d.erase(taskId);
return userId;
}
};
/**
* Your TaskManager object will be instantiated and called as such:
* TaskManager* obj = new TaskManager(tasks);
* obj->add(userId,taskId,priority);
* obj->edit(taskId,newPriority);
* obj->rmv(taskId);
* int param_4 = obj->execTop();
*/
###go
type TaskManager struct {
d map[int][2]int
st *redblacktree.Tree[int, int]
}
func encode(priority, taskId int) int {
return (priority << 32) | taskId
}
func comparator(a, b int) int {
if a > b {
return -1
} else if a < b {
return 1
}
return 0
}
func Constructor(tasks [][]int) TaskManager {
tm := TaskManager{
d: make(map[int][2]int),
st: redblacktree.NewWith[int, int](comparator),
}
for _, task := range tasks {
tm.Add(task[0], task[1], task[2])
}
return tm
}
func (this *TaskManager) Add(userId int, taskId int, priority int) {
this.d[taskId] = [2]int{userId, priority}
this.st.Put(encode(priority, taskId), taskId)
}
func (this *TaskManager) Edit(taskId int, newPriority int) {
if e, ok := this.d[taskId]; ok {
priority := e[1]
this.st.Remove(encode(priority, taskId))
this.d[taskId] = [2]int{e[0], newPriority}
this.st.Put(encode(newPriority, taskId), taskId)
}
}
func (this *TaskManager) Rmv(taskId int) {
if e, ok := this.d[taskId]; ok {
priority := e[1]
delete(this.d, taskId)
this.st.Remove(encode(priority, taskId))
}
}
func (this *TaskManager) ExecTop() int {
if this.st.Empty() {
return -1
}
it := this.st.Iterator()
it.Next()
taskId := it.Value()
if e, ok := this.d[taskId]; ok {
delete(this.d, taskId)
this.st.Remove(it.Key())
return e[0]
}
return -1
}
/**
* Your TaskManager object will be instantiated and called as such:
* obj := Constructor(tasks);
* obj.Add(userId,taskId,priority);
* obj.Edit(taskId,newPriority);
* obj.Rmv(taskId);
* param_4 := obj.ExecTop();
*/
###ts
class TaskManager {
private d: Map<number, [number, number]>;
private pq: PriorityQueue<[number, number]>;
constructor(tasks: number[][]) {
this.d = new Map();
this.pq = new PriorityQueue<[number, number]>((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
}
return b[0] - a[0];
});
for (const task of tasks) {
this.add(task[0], task[1], task[2]);
}
}
add(userId: number, taskId: number, priority: number): void {
this.d.set(taskId, [userId, priority]);
this.pq.enqueue([priority, taskId]);
}
edit(taskId: number, newPriority: number): void {
const e = this.d.get(taskId);
if (!e) return;
const userId = e[0];
this.d.set(taskId, [userId, newPriority]);
this.pq.enqueue([newPriority, taskId]);
}
rmv(taskId: number): void {
this.d.delete(taskId);
}
execTop(): number {
while (!this.pq.isEmpty()) {
const [priority, taskId] = this.pq.dequeue();
const e = this.d.get(taskId);
if (e && e[1] === priority) {
this.d.delete(taskId);
return e[0];
}
}
return -1;
}
}
/**
* Your TaskManager object will be instantiated and called as such:
* var obj = new TaskManager(tasks)
* obj.add(userId,taskId,priority)
* obj.edit(taskId,newPriority)
* obj.rmv(taskId)
* var param_4 = obj.execTop()
*/
时间复杂度方面，初始化操作需要 $O(n \log n)$ 的时间，其中 $n$ 是初始任务的数量。每个添加、编辑、删除和执行操作都需要 $O(\log m)$ 的时间，其中 $m$ 是当前系统中的任务数量。由于总操作次数不超过 $2 \times 10^5$，因此整体时间复杂度是可接受的。空间复杂度 $O(n + m)$，用于存储哈希表和有序集合。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~
