3408. Design Task Manager

Leetcode link

题目简介

题目要求我们实现一个 TaskManager 系统用于管理任务，并实现以下方法：

• add(int userId, int taskId, int priority)
• edit(int taskId, int newPriority)
• rmv(int taskId)
• execTop()

解题思路

这题也是在考我们关于大顶堆的实现

• 在构造函数的时候，我们需要用 map 来建立 task 跟 user 以及 priority 的映射，以及构建好大顶堆
• 在实现 add 方法的时候我们只需要将新的映射 add 进 map 中，并且 push 到大顶堆中就好
• edit 与 add 相似，只是需要从 map 中将原来的映射覆盖，大顶堆中的数据则先搁置不需要删除
• rmv 也是一样的，区别在于要将原来 map 中的 task 删除
• execTop 时，我们需要对比当前大顶堆堆顶的数据是否还在 map 中，如果不是需要重新获取堆顶直到获取到了与 map 数据符合的 task，此时我们返回 userId 并将当前 task 使用 rmv 删除就好

Javascript（自己构建 maxHeap）

/**
 * @param {number[][]} tasks
 */
var TaskManager = function (tasks) {
    this.taskToUserId = new Map()
    this.taskToPriority = new Map()
    this.maxHeap = new MyMaxHeap()

    for (const [userId, taskId, priority] of tasks) {
        this.taskToUserId.set(taskId, userId)
        this.taskToPriority.set(taskId, priority)
        this.maxHeap.push([taskId, priority])
    }
};

/** 
 * @param {number} userId 
 * @param {number} taskId 
 * @param {number} priority
 * @return {void}
 */
TaskManager.prototype.add = function (userId, taskId, priority) {
    this.taskToUserId.set(taskId, userId)
    this.taskToPriority.set(taskId, priority)
    this.maxHeap.push([taskId, priority])
};

/** 
 * @param {number} taskId 
 * @param {number} newPriority
 * @return {void}
 */
TaskManager.prototype.edit = function (taskId, newPriority) {
    this.taskToPriority.set(taskId, newPriority)
    this.maxHeap.push([taskId, newPriority])
};

/** 
 * @param {number} taskId
 * @return {void}
 */
TaskManager.prototype.rmv = function (taskId) {
    this.taskToPriority.delete(taskId)
    this.taskToUserId.delete(taskId)
};

/**
 * @return {number}
 */
TaskManager.prototype.execTop = function () {
    while (!this.maxHeap.isEmpty()) {
        const [taskId, priority] = this.maxHeap.pop()
        if (this.taskToPriority.has(taskId) && priority === this.taskToPriority.get(taskId)) {
            const userId = this.taskToUserId.get(taskId)
            this.rmv(taskId)
            return userId
        }
    }
    return -1
};

class MyMaxHeap {
    constructor() {
        this.heap = []
    }

    isEmpty() {
        return this.heap.length === 0
    }

    peek() {
        return this.heap[0]
    }

    push(item) {
        this.heap.push(item)
        this.heapifyUp(this.heap.length - 1)
    }

    pop() {
        if (this.heap.length <= 1) {
            return this.heap.pop()
        }
        const res = this.peek()
        this.heap[0] = this.heap.pop()
        this.heapifyDown(0)
        return res
    }

    heapifyUp(index) {
        const parent = Math.floor((index - 1) / 2)

        if (parent >= 0 && this.compare(this.heap[parent], this.heap[index]) > 0) {
            [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]
            this.heapifyUp(parent)
        }
    }

    heapifyDown(index) {
        const left = index * 2 + 1
        const right = index * 2 + 2
        let max = index

        if (left < this.heap.length && this.compare(this.heap[left], this.heap[max]) < 0) {
            max = left
        }
        if (right < this.heap.length && this.compare(this.heap[right], this.heap[max]) < 0) {
            max = right
        }

        if (max !== index) {
            [this.heap[max], this.heap[index]] = [this.heap[index], this.heap[max]]
            this.heapifyDown(max)
        }
    }

    compare([taskA, priorityA], [taskB, priorityB]) {
        if (priorityB === priorityA) {
            return taskB - taskA
        }
        return priorityB - priorityA
    }
}

Javascript（使用 PriorityQueue）

/**
 * @param {number[][]} tasks
 */
var TaskManager = function(tasks) {
    this.taskToUserId = new Map()
    this.taskToPriority = new Map()
    this.queue = new PriorityQueue(([taskA, priorityA], [taskB, priorityB]) => {
        if(priorityA === priorityB) {
            return taskB - taskA
        }
        return priorityB - priorityA
    })

    for(const [userId, taskId, priority] of tasks) {
        this.taskToUserId.set(taskId, userId)
        this.taskToPriority.set(taskId, priority)
        this.queue.enqueue([taskId, priority])
    }
};

/** 
 * @param {number} userId 
 * @param {number} taskId 
 * @param {number} priority
 * @return {void}
 */
TaskManager.prototype.add = function(userId, taskId, priority) {
    this.taskToUserId.set(taskId, userId)
    this.taskToPriority.set(taskId, priority)
    this.queue.enqueue([taskId, priority])
};

/** 
 * @param {number} taskId 
 * @param {number} newPriority
 * @return {void}
 */
TaskManager.prototype.edit = function(taskId, newPriority) {
    this.taskToPriority.set(taskId, newPriority)
    this.queue.enqueue([taskId, newPriority])
};

/** 
 * @param {number} taskId
 * @return {void}
 */
TaskManager.prototype.rmv = function(taskId) {
    this.taskToPriority.delete(taskId)
    this.taskToUserId.delete(taskId)
};

/**
 * @return {number}
 */
TaskManager.prototype.execTop = function() {
    while (!this.queue.isEmpty()) {
        const [taskId, priority] = this.queue.dequeue()
        if (this.taskToPriority.has(taskId) && priority === this.taskToPriority.get(taskId)) {
            const userId = this.taskToUserId.get(taskId)
            this.rmv(taskId)
            return userId
        }
    }
    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()
 */