2532.过桥的时间

链接：2532.过桥的时间
难度：Hard
标签：数组、模拟、堆（优先队列）
简介：所有 n 个盒子都需要放入新仓库，请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

题解 1 - typescript

• 编辑时间：2023-01-08
• 执行用时：276ms
• 内存消耗：53MB
• 编程语言：typescript
• 解法介绍：模拟。

class Heap<T = number> {
  public arr: T[] = [];
  get isEmpty() {
    return this.size === 0;
  }
  get size() {
    return this.arr.length;
  }
  get top() {
    return this.arr[0];
  }
  constructor(public compare: (t1: T, t2: T) => number) {}
  add(num: T): void {
    this.arr.push(num);
    this.shiftUp(this.size - 1);
  }
  remove(): T {
    const num = this.arr.shift()!;
    if (this.size) {
      this.arr.unshift(this.arr.pop()!);
      this.shiftDown(0);
    }
    return num;
  }
  private shiftUp(index: number): void {
    if (index === 0) return;
    const parentIndex = (index - 1) >> 1;
    if (this.compare(this.arr[index], this.arr[parentIndex]) > 0) {
      [this.arr[index], this.arr[parentIndex]] = [this.arr[parentIndex], this.arr[index]];
      this.shiftUp(parentIndex);
    }
  }
  private shiftDown(index: number): void {
    let childrenIndex = index * 2 + 1;
    if (childrenIndex > this.size - 1) return;
    if (
      childrenIndex + 1 <= this.size - 1 &&
      this.compare(this.arr[childrenIndex + 1], this.arr[childrenIndex]) > 0
    ) {
      childrenIndex++;
    }
    if (this.compare(this.arr[childrenIndex], this.arr[index]) > 0) {
      [this.arr[childrenIndex], this.arr[index]] = [this.arr[index], this.arr[childrenIndex]];
      this.shiftDown(childrenIndex);
    }
  }
  *[Symbol.iterator](): IterableIterator<T> {
    for (const t of this.arr) {
      yield t;
    }
  }
}
class TWorker {
  constructor(
    public i: number,
    public l2r: number,
    public pickOld: number,
    public r2l: number,
    public putNew: number,
    public wait: number = 0
  ) {}
  cost() {
    return this.l2r + this.r2l;
  }
  cmp(worker: TWorker) {
    return this.cost() !== worker.cost() ? this.cost() - worker.cost() : this.i - worker.i;
  }
  cmpWait(worker: TWorker) {
    return worker.wait - this.wait;
  }
  toString() {
    return `Worker${this.i}: l2r=${this.l2r}, r2l=${this.r2l}, pickOld=${this.pickOld}, putNew=${
      this.putNew
    }, cost=${this.cost()}, wait = ${this.wait}`;
  }
}
function findCrossingTime(n: number, k: number, time: number[][]): number {
  const workers = new Array(k)
    .fill(0)
    .map((_, i) => new TWorker(i, ...(time[i] as [number, number, number, number])));
  console.log('========');
  console.log(workers.map(v => v.toString()).join('
'));
  console.log('========');
  const lHeap = new Heap<TWorker>((w1, w2) => w1.cmp(w2));
  const rHeap = new Heap<TWorker>((w1, w2) => w1.cmp(w2));
  const pickHeap = new Heap<TWorker>((t1, t2) => t1.cmpWait(t2));
  const putHeap = new Heap<TWorker>((t1, t2) => t1.cmpWait(t2));
  const printHeap = (record: Record<string, Heap<TWorker>>) =>
    Object.entries(record).forEach(([k, v]) =>
      console.log(`=> ${k}(${v.size}):
${v.arr.map(v => v.toString()).join('
')}`)
    );
  for (const worker of workers) lHeap.add(worker);
  let ans = 0;
  while (n) {
    console.log('=====loop====');
    console.log(`ans = ${ans}, n = ${n}`);
    printHeap({ lHeap, rHeap, pickHeap, putHeap });
    while (pickHeap.size && pickHeap.top.wait <= ans) rHeap.add(pickHeap.remove());
    while (putHeap.size && putHeap.top.wait <= ans) lHeap.add(putHeap.remove());
    if (lHeap.isEmpty && rHeap.isEmpty) {
      const pick = pickHeap.top?.wait ?? Infinity;
      const put = putHeap.top?.wait ?? Infinity;
      if (pick < put) ans = pickHeap.top.wait;
      else ans = putHeap.top.wait;
      while (pickHeap.size && pickHeap.top[0] <= ans) rHeap.add(pickHeap.remove()), n--;
      while (putHeap.size && putHeap.top[0] <= ans) lHeap.add(putHeap.remove());
    }
    if (rHeap.size) {
      ans += rHeap.top.r2l;
      const worker = rHeap.remove();
      worker.wait = ans + worker.putNew;
      putHeap.add(worker);
    } else if (lHeap.size && n) {
      ans += lHeap.top.l2r;
      const worker = lHeap.remove();
      worker.wait = ans + worker.pickOld;
      pickHeap.add(worker);
      n--;
    }
  }
  while (rHeap.size || pickHeap.size) {
    console.log('=====after====');
    console.log(`ans = ${ans}, n = ${n}`);
    printHeap({ lHeap, rHeap, pickHeap, putHeap });
    if (rHeap.size) ans += rHeap.remove().r2l;
    while (pickHeap.size && pickHeap.top.wait <= ans) rHeap.add(pickHeap.remove());
    if (rHeap.isEmpty && pickHeap.size) ans = pickHeap.top.wait;
  }
  return ans;
}

题解 2 - rust

• 编辑时间：2023-01-08
• 执行用时：36ms
• 内存消耗：3.6MB
• 编程语言：rust
• 解法介绍：同上。

use std::{cmp::Ordering, collections::BinaryHeap};
#[derive(Eq, Ord, PartialEq)]
struct Worker {
    i: i32,
    l2r: i32,
    pick_old: i32,
    r2l: i32,
    put_new: i32,
    wait: i32,
    mode: bool,
}
impl Worker {
    fn new(i: i32, l2r: i32, pick_old: i32, r2l: i32, put_new: i32) -> Self {
        Worker {
            i,
            l2r,
            pick_old,
            r2l,
            put_new,
            wait: 0,
            mode: true,
        }
    }
    fn cost(&self) -> i32 {
        self.l2r + self.r2l
    }
    fn cmp(&self, worker: &Worker) -> Ordering {
        if self.mode {
            self.cmp_bridge(worker)
        } else {
            self.cmp_wait(worker)
        }
    }
    fn cmp_bridge(&self, worker: &Worker) -> Ordering {
        if self.cost() != worker.cost() {
            self.cost().cmp(&worker.cost())
        } else {
            self.i.cmp(&worker.i)
        }
    }
    fn cmp_wait(&self, worker: &Worker) -> Ordering {
        worker.wait.cmp(&self.wait)
    }
    fn set_mode(&mut self, mode: bool) {
        self.mode = mode;
    }
    fn set_bridge_mode(&mut self) {
        self.set_mode(true)
    }
    fn set_wait_mode(&mut self) {
        self.set_mode(false)
    }
}
impl ToString for Worker {
    fn to_string(&self) -> String {
        return format!(
            "Worker{}: l2r = {}, r2l = {}, pickOld = {}, putNew = {}, cost = {}, wait = {}",
            self.i,
            self.l2r,
            self.r2l,
            self.pick_old,
            self.put_new,
            self.cost(),
            self.wait
        );
    }
}
impl PartialOrd for Worker {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
fn printHeap(name: &'static str, heap: &BinaryHeap<Worker>) {
    println!("=> {name}({})", heap.len());
    for item in heap.iter() {
        println!("{}", item.to_string());
    }
}
impl Solution {
    pub fn find_crossing_time(n: i32, k: i32, time: Vec<Vec<i32>>) -> i32 {
        let mut n = n;
        let mut workers = Vec::new();
        for i in 0..time.len() {
            workers.push(Worker::new(
                i as i32, time[i][0], time[i][1], time[i][2], time[i][3],
            ));
        }
        let mut left_heap = BinaryHeap::<Worker>::new();
        let mut right_heap = BinaryHeap::<Worker>::new();
        let mut pick_heap = BinaryHeap::<Worker>::new();
        let mut put_heap = BinaryHeap::<Worker>::new();
        for worker in workers {
            left_heap.push(worker);
        }
        let mut ans = 0;
        while n > 0 {
            // println!("====loop====");
            // println!("ans = {ans}, n = {n}");
            // printHeap("left_heap", &left_heap);
            // printHeap("right_heap", &right_heap);
            // printHeap("pick_heap", &pick_heap);
            // printHeap("put_heap", &put_heap);
            while !pick_heap.is_empty() && pick_heap.peek().unwrap().wait <= ans {
                let mut worker = pick_heap.pop().unwrap();
                worker.set_bridge_mode();
                right_heap.push(worker);
            }
            while !put_heap.is_empty() && put_heap.peek().unwrap().wait <= ans {
                let mut worker = put_heap.pop().unwrap();
                worker.set_bridge_mode();
                left_heap.push(worker);
            }
            if left_heap.is_empty() && right_heap.is_empty() {
                let pick = match pick_heap.peek() {
                    Some(worker) => worker.wait,
                    None => i32::MAX,
                };
                let put = match put_heap.peek() {
                    Some(worker) => worker.wait,
                    None => i32::MAX,
                };
                ans = pick.min(put);
            }
            if !right_heap.is_empty() {
                let mut worker = right_heap.pop().unwrap();
                ans += worker.r2l;
                worker.wait = ans + worker.put_new;
                worker.set_wait_mode();
                put_heap.push(worker);
            } else if !left_heap.is_empty() && n > 0 {
                let mut worker = left_heap.pop().unwrap();
                ans += worker.l2r;
                worker.wait = ans + worker.pick_old;
                worker.set_wait_mode();
                pick_heap.push(worker);
                n -= 1;
            }
        }
        while !right_heap.is_empty() || !pick_heap.is_empty() {
            // println!("====after====");
            // println!("ans = {ans}, n = {n}");
            // printHeap("left_heap", &left_heap);
            // printHeap("right_heap", &right_heap);
            // printHeap("pick_heap", &pick_heap);
            // printHeap("put_heap", &put_heap);
            if !right_heap.is_empty() {
                ans += right_heap.pop().unwrap().r2l;
            }
            while !pick_heap.is_empty() && pick_heap.peek().unwrap().wait <= ans {
                let mut worker = pick_heap.pop().unwrap();
                worker.set_bridge_mode();
                right_heap.push(worker);
            }
            if right_heap.is_empty() && !pick_heap.is_empty() {
                ans = pick_heap.peek().unwrap().wait;
            }
        }
        ans
    }
}

题解 3 - cpp

• 编辑时间：2023-07-07
• 执行用时：188ms
• 内存消耗：20.5MB
• 编程语言：cpp
• 解法介绍：模拟。

#define X first
#define Y second
class Solution {
public:
    typedef pair<int, int> pii;
    int findCrossingTime(int n, int k, vector<vector<int>>& time) {
        auto cmp = [&](int i1, int i2) {
            int v1 = time[i1][0] + time[i1][2], v2 = time[i2][0] + time[i2][2];
            return v1 < v2 || v1 == v2 && i1 < i2;
        };
        priority_queue<int, vector<int>, decltype(cmp)> ql(cmp), qr(cmp);
        for (int i = 0; i < k; i++) ql.push(i);
        auto cmpp = [&](pii i1, pii i2) {
            return i2.X < i1.X;
        };
        priority_queue<pii, vector<pii>, decltype(cmpp)> qpl(cmpp), qpr(cmpp);
        int res = 0;
        while (qr.size() || qpr.size() || n > 0) {
            // cout << "===> Loop: " 
            //      << "n = " << n
            //      << ", res = " << res
            //      << ", qpl = " << (qpl.size() ? (long long)qpl.top().X * 100 + qpl.top().Y : -1)
            //      << ", ql = " << (ql.size() ? ql.top() : -1)
            //      << ", qr = " << (qr.size() ? qr.top() : -1)
            //      << ", qpr = " << (qpr.size() ? (long long)qpr.top().X * 100 + qpr.top().Y : -1)
            //      << endl;
            if ((ql.empty() && qr.empty()) || qr.empty() && qpr.size() && n == 0) {
                res = max(
                    res,
                    min(
                        qpl.size() ? qpl.top().X : INT_MAX,
                        qpr.size() ? qpr.top().X : INT_MAX
                    )
                );
            }
            while (qpl.size() && qpl.top().X <= res) {
                auto cur = qpl.top();
                qpl.pop();
                ql.push(cur.Y);
            }
            while (qpr.size() && qpr.top().X <= res) {
                auto cur = qpr.top();
                qpr.pop();
                qr.push(cur.Y);
            }
            if (qr.size()) {
                auto cur = qr.top();
                qr.pop();
                res += time[cur][2];
                qpl.push(make_pair(res + time[cur][3], cur));
            } else if (ql.size() && n > 0) {
                n -= 1;
                auto cur = ql.top();
                ql.pop();
                res += time[cur][0];
                qpr.push(make_pair(res + time[cur][1], cur));
            }
        }
        return res;
    }
};