Skip to content

Latest commit

 

History

History
564 lines (529 loc) · 15.5 KB

1606.找到处理最多请求的服务器.md

File metadata and controls

564 lines (529 loc) · 15.5 KB

1606.找到处理最多请求的服务器

/*
 * @lc app=leetcode.cn id=1606 lang=typescript
 *
 * [1606] 找到处理最多请求的服务器
 */

// @lc code=start
function busiestServers(k: number, arrival: number[], load: number[]): number[] {}
// @lc code=end

解法 1: 使用 BST

function busiestServers(k: number, arrival: number[], load: number[]): number[] {
  const available = new BinarySearchTree(),
    time = new BinarySearchTree<[number, number]>((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]))
  for (let i = 0; i < k; i++) {
    available.insert(i)
  }
  const count: number[] = new Array(k).fill(0)
  for (let i = 0; i < arrival.length; i++) {
    const start = arrival[i],
      end = start + load[i]
    while (time.size() && time.getMin()![0] <= start) {
      const min = time.getMin()!
      time.delete(min)
      available.insert(min[1])
    }

    let server = available.ceiling(i % k)
    if (server === null) {
      server = available.ceiling(0)
    }

    if (server !== null) {
      available.delete(server)
      time.insert([end, server])
      count[server]++
    }
  }
  let res: number[] = [],
    max = 0
  for (let i = 0; i < k; i++) {
    if (max === count[i]) res.push(i)
    if (max < count[i]) {
      max = count[i]
      res = [i]
    }
  }

  return res
}

interface Node<T = number> {
  id: number
  val: T
  size: number
  height: number
  count: number
  left: Node<T> | null
  right: Node<T> | null
}
/**
 * @see https://github.com/XYShaoKang/sk-js-algorithm
 */
class BinarySearchTree<T = number> {
  private root: Node<T> | null = null
  /**
   * 不重复数字的个数
   */
  private length = 0
  private min: T | null = null
  private max: T | null = null
  private minCache = true
  private maxCache = true
  constructor(...args: T extends number ? [((a: number, b: number) => number)?] : [(a: T, b: T) => number])
  constructor(private _compare: (a: T, b: T) => number = ((a: number, b: number) => a - b) as any) {
    this.compare = this.compare.bind(this)
  }
  private isT(t: T | undefined | null): t is T {
    return t !== undefined && t !== null
  }
  private compare(a: T | null | undefined, b: T | null | undefined) {
    const { isT } = this
    if (isT(a) && isT(b)) return this._compare(a, b)

    if (isT(a)) return 1
    if (isT(b)) return -1
    return 0
  }
  /** 判断是否为空
   * @returns
   */
  isEmpty() {
    return !this.root
  }
  /** 获取所有元素个数,统计的是包含所有重复数字的数量
   * @returns
   */
  size() {
    return this.root ? this.root.size : 0
  }
  /** 返回树的 root 元素
   *
   * @returns
   */
  getRoot() {
    return this.root
  }
  /** # 返回最小值
   *  如果之前发生删除,并且删除的数等于最小值,则会在下次获取最小值时,重新查找最小值,并缓存最小值
   *  否则直接返回缓存中的最小值
   * @returns
   */
  getMin(): T | null {
    if (this.minCache) {
      return this.min
    }
    const min = this.searchKth(this.size())
    this.min = min
    this.minCache = true
    return min
  }
  /** # 返回最大值
   *  如果之前发生删除,并且删除的数等于最大值,则会在下次获取最大值时,重新查找最大值,并缓存最大值
   *  否则直接返回缓存中的最大值
   * @returns
   */
  getMax(): T | null {
    if (this.maxCache) {
      return this.max
    }
    const max = this.searchKth(1)
    this.max = max
    this.maxCache = true
    return max
  }

  //#region balance
  /**
   * 平衡操作
   * @param node 失衡的根结点
   * @returns 返回平衡之后的根结点
   */
  private balance(node: Node<T>): Node<T> {
    node.height = this.getHeight(node)
    const blance = this.getBalance(node)
    // node.height = Math.max(leftH, rightH) + 1
    let res
    // 平衡
    if (Math.abs(blance) === 2) {
      if (blance > 0) {
        const heightDif = (node.left?.left?.height ?? 0) - (node.left?.right?.height ?? 0)
        if (heightDif > 0) {
          // 左左
          res = this.rotateRight(node)
        } else if (heightDif < 0) {
          // 左右
          res = this.rotateLeftRight(node)
        }
      } else {
        const heightDif = (node.right?.left?.height ?? 0) - (node.right?.right?.height ?? 0)
        if (heightDif > 0) {
          // 右左
          res = this.rotateRightLeft(node)
        } else if (heightDif < 0) {
          // 右右
          res = this.rotateLeft(node)
        }
      }
    }
    return res ? res : node
  }
  private rotateRight(node: Node<T>) {
    const left = node.left!
    const leftRight = left.right

    left.right = node
    node.left = leftRight

    node.height = this.getHeight(node)
    left.height = this.getHeight(left)
    node.size = this.getSize(node)
    left.size = this.getSize(left)

    return left
  }
  private rotateLeft(node: Node<T>) {
    const right = node.right!
    const rightLeft = right.left

    right.left = node
    node.right = rightLeft

    node.height = this.getHeight(node)
    right.height = this.getHeight(right)
    node.size = this.getSize(node)
    right.size = this.getSize(right)

    return right
  }
  private rotateLeftRight(node: Node<T>) {
    node.left = this.rotateLeft(node.left!)
    return this.rotateRight(node)
  }
  private rotateRightLeft(node: Node<T>) {
    node.right = this.rotateRight(node.right!)
    return this.rotateLeft(node)
  }

  //#endregion

  private getBalance(node: Node<T>) {
    return this.getHeight(node.left) - this.getHeight(node.right)
  }
  private getHeight(node: Node<T> | null) {
    if (!node) return 0
    return Math.max(node.left?.height ?? 0, node.right?.height ?? 0) + 1
  }
  private getSize(node: Node<T> | null) {
    if (!node) return 0
    return (node.left?.size ?? 0) + (node.right?.size ?? 0) + node.count
  }
  private createNode(val: T): Node<T> {
    return { id: Math.random() * new Date().valueOf(), val, left: null, right: null, size: 1, height: 1, count: 1 }
  }

  /** 插入元素
   *
   * @param val
   */
  insert(val: T) {
    let cur = this.createNode(val)
    if (this.isEmpty()) {
      this.root = cur
      this.length++
    } else {
      ;[, cur] = this.insertNode(this.root!, cur)
    }

    if (this.min === null || this.compare(this.min, val) > 0) {
      this.min = val
    }
    if (this.max === null || this.compare(this.max, val) < 0) {
      this.max = val
    }
    return cur
  }
  /**
   *
   * @param node 当前遍历的结点
   * @param cur 需要插入的结点
   * @param parent 当前结点的父节点
   * @returns 返回包含一个 boolean 值,用来标记是否需要重平衡,以及插入的 Node,如果是重复值,则返回已经存在的那个 Node
   */
  private insertNode(node: Node<T>, cur: Node<T>, parent: Node<T> | null = null): [boolean, Node<T>] {
    node.size++
    const compareResult = this.compare(cur.val, node.val)
    let res: [boolean, Node<T>] | undefined
    if (compareResult === 0) {
      // 要插入的结点比当前结点相等,既元素已存在,只需更新 count
      node.count++
      // 只是增加计数,不会对平衡性造成影响,所以不需要重新平衡
      return [false, node]
    } else if (compareResult > 0) {
      // 要插入的结点比当前结点大,则需要插入到右子树中
      if (node.right) {
        res = this.insertNode(node.right, cur, node)
        if (!res[0]) return res
      } else {
        node.right = cur
        this.length++
        res = [true, cur]
      }
    } else {
      // 要插入的结点比当前结点小,则需要插入到左子树中
      if (node.left) {
        res = this.insertNode(node.left, cur, node)
        if (!res[0]) return res
      } else {
        node.left = cur
        this.length++
        res = [true, cur]
      }
    }

    // 平衡操作
    // 优化: 使用 res[0] 标志判断是否需要进行平衡
    // 对于新添加的结点,总是需要进行平衡
    // 如果发现某个子树平衡前后的没有变化,树的高度也没有变化,则后续祖先结点不需要进行平衡操作
    let preHeight = node.height
    const newNode = this.balance(node)
    if (newNode === node && node.height === preHeight) {
      // 当前根结点以及树高度没有发生变化,则后续不需要进行平衡
      res = [false, res[1]]
    } else if (newNode !== node) {
      // 当前元素发生变化,对于插入来说,只会调整一次,后续不需要变化
      if (parent) {
        parent.left === node ? (parent.left = newNode) : (parent.right = newNode)
      } else {
        this.root = newNode
      }
      res = [false, res[1]]
    }
    return res
  }

  /** 删除元素
   *
   * @param val
   * @returns
   */
  delete(val: T) {
    if (!this.root) return
    this.deleteNode(val, this.root, null)
  }

  private deleteNode(val: T, node: Node<T> | null, parent: Node<T> | null): Node<T> | null {
    if (!node) return null

    let res = this.compare(val, node.val)
    if (res === 0) {
      // 找到要删除的元素
      node.count--
      node.size--
      // 存在多个当前元素,所以只是减去计数,并不需要改变结构
      if (node.count > 0) return node

      if (!node.left || !node.right) {
        if (this.min === val) {
          this.minCache = false
        }
        if (this.max === val) {
          this.maxCache = false
        }
        this.length--
        // 只有一个子结点或者没有子结点,则直接返回子结点即可
        if (!parent) {
          this.root = node.left ?? node.right!
          return this.root
        } else {
          return node.left ?? node.right!
        }
      } else {
        // 同时存在左右结点,则需要找到一个值放到当前位置,然后删除那个值
        // 这个值可以是比当前值大的最小值,也可以是比当前值小的最大值
        // 这里根据左右子树的高度进行选择
        const selectLeft = node.left.height > node.right.height
        let replaceNode = selectLeft ? this.pre(node)! : this.next(node)!,
          name: 'left' | 'right' = selectLeft ? 'left' : 'right'

        node.val = replaceNode.val
        node.count = replaceNode.count
        replaceNode.count = 0
        node[name] = this.deleteNode(replaceNode.val, node[name], node)
      }
    } else if (res > 0) {
      node.right = this.deleteNode(val, node.right, node)
    } else {
      node.left = this.deleteNode(val, node.left, node)
    }

    // 重新计算 size
    node.size = this.getSize(node)

    let preHeight = node.height
    const newNode = this.balance(node)
    if (parent) {
      parent.left === node ? (parent.left = newNode) : (parent.right = newNode)
    } else {
      this.root = newNode
    }

    return newNode
  }

  // 删除操作时,获取替代当前结点的结点
  private next(node: Node<T>) {
    let next = node.right
    while (next?.left) {
      next = next.left
    }
    return next
  }
  private pre(node: Node<T>) {
    let pre = node.left
    while (pre?.right) {
      pre = pre.right
    }
    return pre
  }

  /** 查找第一个大于等于 val 的值
   *
   * @param val
   * @param compare
   * @returns
   */
  search(val: T, compare?: (a: T, b: T) => number) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchCeilingNode(this.root!, val, compare ?? this.compare)
    return node.val
  }
  private searchCeilingNode(
    node: Node<T>,
    val: T,
    compare: (a: T, b: T) => number,
    parent: Node<T> | null = null,
  ): [Node<T> | null, Node<T>] {
    const res = compare(val, node.val)
    if (res === 0) {
      return [parent, node]
    } else if (res > 0) {
      if (node.right) {
        return this.searchCeilingNode(node.right, val, compare, node)
      } else {
        return [parent, node]
      }
    } else {
      if (node.left) {
        const [p, value] = this.searchCeilingNode(node.left, val, compare, node)
        if (compare(value.val, val) < 0) {
          return [parent, node]
        } else {
          return [p, value]
        }
      } else {
        return [parent, node]
      }
    }
  }
  /** 获取大于等于 val 的最小值
   *
   * @param val
   * @returns
   */
  ceiling(val: T) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchCeilingNode(this.root!, val, this.compare)
    return this.compare(node.val, val) >= 0 ? node.val : null
  }
  private searchFloorNode(
    node: Node<T>,
    val: T,
    compare: (a: T, b: T) => number,
    parent: Node<T> | null = null,
  ): [Node<T> | null, Node<T>] {
    const res = compare(val, node.val)
    if (res === 0) {
      return [parent, node]
    } else if (res > 0) {
      if (node.right) {
        const [p, value] = this.searchFloorNode(node.right, val, compare, node)
        if (compare(value.val, val) > 0) {
          return [parent, node]
        } else {
          return [p, value]
        }
      } else {
        return [parent, node]
      }
    } else {
      if (node.left) {
        return this.searchFloorNode(node.left, val, compare, node)
      } else {
        return [parent, node]
      }
    }
  }
  /** 获取小于等于 val 的最大值
   *
   * @param val
   * @returns
   */
  floor(val: T) {
    if (this.isEmpty()) {
      return null
    }
    const [, node] = this.searchFloorNode(this.root!, val, this.compare)
    return this.compare(node.val, val) <= 0 ? node.val : null
  }

  /** 获取第 k 个元素的值,k 从 1 开始,如果 k 超出边界,返回 null
   *
   * @param k
   * @returns
   */
  searchKth(k: number) {
    if (this.isEmpty()) {
      return null
    }
    if (k <= 0 || k > this.size()) {
      return null
    }
    const node = this.searchNodeKth(this.root!, k)
    return node.val
  }
  private searchNodeKth(node: Node<T>, k: number): Node<T> {
    const rSize = node.right?.size ?? 0
    if (rSize === k - 1 || (rSize < k && rSize + node.count >= k)) return node
    if (node.right && rSize > k - 1) return this.searchNodeKth(node.right, k)
    else return this.searchNodeKth(node.left!, k - (node.right?.size ?? 0) - node.count)
  }

  /** 统计大于等于 val 的个数
   *
   * @param val 需要统计的值
   * @returns
   */
  countGreaterThanEq(val: T) {
    if (!this.root) return 0
    return this.countCompare(val, (a, b) => this._compare(a, b), this.root)
  }
  private countCompare(val: T, compare: (a: T, b: T) => number, node: Node<T>, pre = 0): number {
    const res = compare(val, node.val)
    if (res === 0) {
      return pre + (node.right?.size ?? 0) + node.count
    } else if (res > 0) {
      if (node.right) {
        return this.countCompare(val, compare, node.right, pre)
      } else {
        return pre
      }
    } else {
      let count = pre + (node.right?.size ?? 0) + node.count
      if (node.left) {
        return this.countCompare(val, compare, node.left, count)
      } else {
        return count
      }
    }
  }
}

Case

test.each([
  { input: { k: 2, arrival: [1, 2, 3], load: [1000000000, 1, 1000000000] }, output: [1] },
  {
    input: {
      k: 7,
      arrival: [1, 3, 4, 5, 6, 11, 12, 13, 15, 19, 20, 21, 23, 25, 31, 32],
      load: [9, 16, 14, 1, 5, 15, 6, 10, 1, 1, 7, 5, 11, 4, 4, 6],
    },
    output: [0],
  },
  { input: { k: 2, arrival: [2, 3, 4, 8], load: [3, 2, 4, 3] }, output: [1] },
  { input: { k: 3, arrival: [1, 2, 3, 4, 5], load: [5, 2, 3, 3, 3] }, output: [1] },
  { input: { k: 3, arrival: [1, 2, 3, 4], load: [1, 2, 1, 2] }, output: [0] },
  { input: { k: 3, arrival: [1, 2, 3], load: [10, 12, 11] }, output: [0, 1, 2] },
])('input: k = $input.k, arrival = $input.arrival, load = $input.load', ({ input: { k, arrival, load }, output }) => {
  expect(busiestServers(k, arrival, load)).toEqual(output)
})