w_inter

针对加权区间调度问题的一对求解器。

特性

• 无外部依赖，尽管需要分配器（目前还不是可选的）。
• 灵活：任何实现了 Ord + Add + Clone 的类型都可以视为区间边界或权重类型。
• 高效：运行在 O(n log n) 的时间复杂度下。
• 快速：提供缓存感知、零分配的 API。

简单示例

                   3───────────┐
                   └───────────┘
               8───────────────────┐
               └───────────────────┘
       5───────────┐   7───────────────┐
       └───────────┘   └───────────────┘
   3───────────────────────┐       4───────────┐
   └───────────────────────┘       └───────────┘
   2───┐       5───────┐   3───────────────┐
   └───┘       └───────┘   └───────────────┘
◀──0───1───2───3───4───5───6───7───8───9───10──11──▶

let intervals = vec![
  (0u8, 1u8,  2u8).into(), // (start, end, weight)
  (0u8, 6u8,  3u8).into(),
  (1u8, 4u8,  5u8).into(),
  (3u8, 5u8,  5u8).into(),
  (3u8, 8u8,  8u8).into(),
  (4u8, 7u8,  3u8).into(),
  (5u8, 9u8,  7u8).into(),
  (6u8, 10u8, 3u8).into(),
  (8u8, 11u8, 4u8).into()
];

let optimal = unsorted(&intervals);

assert_eq!(
  optimal,
  vec![
    (1u8, 4u8, 5u8).into(),
    (5u8, 9u8, 7u8).into()
  ]
);

快速（摊销分配）示例

// our goal is to allocate once and reuse the same buffers
// measure (or apply a guess) to avoid having to resize the vector.
let max_interval_count = problems.iter().map(|i| i.len()).max();

// we can say with certainty that the memo buffer
// will never need to be larger than the largest input size.
let mut memo = vec![0u8; max_interval_count];

// we don't know how big the solution set will be,
// but it can't be larger than the largest input size.
let mut soln = Vec::with_capacity(max_interval_count);

for intervals in problems {
  // perhaps we know our intervals to be *almost* sorted,
  // so we choose to use an algorithm tuned for this case.
  sort(&mut intervals);

  // we don't strictly need to, but we clear the old solution set,
  // so that only the optimal set from this run ends up in the buffer.
  soln.clear();

  sorted(
    &intervals,
    &mut memo,
    &mut soln
  );

  // we can now use the `soln` buffer before it's recycled
}

许可证：MIT