2532.过桥的时间.md

2532.过桥的时间

/*
 * @lc app=leetcode.cn id=2532 lang=typescript
 *
 * [2532] 过桥的时间
 */

// @lc code=start
function findCrossingTime(n: number, k: number, time: number[][]): number {}
// @lc code=end

解法 1: 堆模拟

function findCrossingTime(n: number, k: number, time: number[][]): number {
  // a b 分别表示：左边桥头、右边桥头
  const [a, b] = Array.from(
    { length: 4 },
    () =>
      new Heap<number>((i, j) => {
        const a = time[i][0] + time[i][2],
          b = time[j][0] + time[j][2]
        if (a !== b) return b - a
        return j - i
      }),
  )

  // c d 分别表示：左边仓库、右边仓库
  const [c, d] = Array.from({ length: 4 }, () => new Heap<[number, number]>((a, b) => a[1] - b[1]))
  for (let i = 0; i < k; i++) a.push(i)
  let cur = 0
  while (n) {
    while (c.size() && c.top()![1] <= cur) {
      const [j] = c.pop()!
      a.push(j)
    }
    while (d.size() && d.top()![1] <= cur) {
      const [j] = d.pop()!
      b.push(j)
    }
    if (b.size()) {
      const j = b.pop()!
      c.push([j, cur + time[j][2] + time[j][3]])
      cur += time[j][2]
    } else if (a.size()) {
      const j = a.pop()!
      d.push([j, cur + time[j][0] + time[j][1]])
      cur += time[j][0]
      n--
    } else {
      cur = Math.min(c.top()?.[1] ?? Infinity, d.top()?.[1] ?? Infinity)
    }
  }

  while (b.size() || d.size()) {
    while (d.size() && d.top()![1] <= cur) b.push(d.pop()![0])
    if (b.size()) {
      const j = b.pop()!
      cur += time[j][2]
    } else {
      cur = d.top()![1]
    }
  }
  return cur
}

class Heap<T = number> {
  private _heap: T[] = []
  public constructor(
    ...args: T extends number ? [((a: number, b: number) => number)?, T[]?] : [(a: T, b: T) => number, T[]?]
  )
  public constructor(
    private _comparator: (n1: T, n2: T) => number = ((a: number, b: number) => a - b) as any,
    arr?: T[],
  ) {
    if (arr) {
      this._heap = [...arr]
      for (let i = arr.length >> 1; i; i--) this.down(i)
    }
  }
  private swap(i: number, j: number) {
    ;[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
  private _has(i: number) {
    return Object.prototype.hasOwnProperty.call(this._heap, i)
  }
  private comparator(i: number, j: number) {
    return this._comparator(this._heap[i], this._heap[j]) < 0
  }
  private parent(i: number) {
    return (i - 1) >> 1
  }
  private children(i: number) {
    return [2 * i + 1, 2 * i + 2]
  }
  private up(i: number) {
    let parent = this.parent(i)
    while (i > 0 && this.comparator(i, parent)) {
      this.swap(i, parent)
      ;[i, parent] = [parent, (parent - 1) >> 1]
    }
  }
  private down(i: number) {
    let [left, right] = this.children(i)

    while (left < this._heap.length) {
      if (!this._has(right)) right = left
      if (this.comparator(right, left)) [left, right] = [right, left]
      if (this.comparator(i, left)) break

      this.swap(i, left)
      i = left
      ;[left, right] = [2 * i + 1, 2 * i + 2]
    }
  }
  public push(node: T) {
    this._heap.push(node)
    this.up(this._heap.length - 1)
  }
  public pop() {
    if (this.size() === 0) return null

    const res = this._heap[0]
    this.swap(0, this._heap.length - 1)
    this._heap.pop()
    this.down(0)
    return res
  }
  public remove(i: number) {
    if (i >= this.size()) return

    const res = this._heap[i]
    this.swap(i, this._heap.length - 1)
    this._heap.pop()

    this.down(i)
    this.up(i)

    return res
  }
  public modify(i: number, val: T) {
    if (i >= this.size()) return

    const res = this._heap[i]
    this._heap[i] = val

    this.down(i)
    this.up(i)
    return res
  }
  public top() {
    if (this.size() === 0) return null

    return this._heap[0]
  }
  public size() {
    return this._heap.length
  }
}

Case

test.each([
  {
    input: {
      n: 10,
      k: 6,
      time: [
        [2, 10, 5, 8],
        [3, 5, 2, 2],
        [5, 8, 10, 10],
        [7, 8, 8, 5],
        [5, 6, 6, 10],
        [6, 10, 6, 2],
      ],
    },
    output: 149,
  },
  {
    input: {
      n: 1,
      k: 3,
      time: [
        [1, 1, 2, 1],
        [1, 1, 3, 1],
        [1, 1, 4, 1],
      ],
    },
    output: 6,
  },
  {
    input: {
      n: 3,
      k: 2,
      time: [
        [1, 9, 1, 8],
        [10, 10, 10, 10],
      ],
    },
    output: 50,
  },
])('input: n = $input.n, k = $input.k, time = $input.time', ({ input: { n, k, time }, output }) => {
  expect(findCrossingTime(n, k, time)).toEqual(output)
})