feat(treeset): support reverse traverse the tree set

upupming commented 2 years ago

LeetCode 题目: https://leetcode.com/problems/maximum-number-of-tasks-you-can-assign/submissions/

这个题目按照智颠老师的解法需要用到类似 C++ 的 end() 这个功能（不过其实用 lower_bould 也可以解），但是我们的 set 现在只能正向遍历，拿不到最大的数。因此添加了这个功能

这道题的 TS 代码：

function maxTaskAssign (tasks: number[], workers: number[], pills: number, strength: number): number {
  const n = tasks.length
  tasks.sort((a, b) => a - b)
  workers.sort((a, b) => a - b)
  let [l, r] = [0, n]
  while (l < r) {
    const mid = l + r + 1 >> 1
    if (valid(mid)) l = mid
    else r = mid - 1
  }
  return l
  function valid (cnt: number) {
    const s = new TreeMultiSet(workers)
    let rest = pills
    for (let i = cnt - 1; i >= 0; i--) {
      // 这里其实直接用 rvalues() 拿最大的 worker 就行了(因为留下来也是浪费，只能去处理更小的 task 了，用最大的 worker 不会更坏)，也可以用最后一个元素判断是否 >= task[i]
      let v = s.ceiling(tasks[i])
      if (v != null) { s.delete(v)
        // console.log(cnt, i, tasks[i], v, 'cnt', s.count(v))
      }
      else {
        // 找到最小的 worker, worker + strength 刚好能够到达
        v = s.ceiling(tasks[i] - strength)
        if (rest && v != null) {
          rest--
          s.delete(v)
          console.log(cnt, i, tasks[i], v, strength)
        } else {
          return false
        }
      }
    }
    return true
  }
};

另外添加了 tsup 配置，现在编译速度更加快了。