Crate w_inter

Source
Expand description

A pair of solvers for the Weighted Interval Scheduling Problem.

§Features
  • Zero external dependencies, although requires an allocator (not optional yet).
  • Flexible: anything implementing Ord + Add + Clone may be thought of as an interval bound or a weight type.
  • Efficient: running in O(n log n).
  • Fast: cache-aware, zero-reallocation APIs are available.
§Simple Example
                   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()
  ]
);
§Fast (Amortized Allocation) Example
// 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
}

Structs§

Traits§

  • Interval
    If a type is Interval, it has bounds over a 1-dimensional domain.
  • Weighted
    If a type is Weighted, it has some number-like value associated with it.

Functions§

  • sorted
    Faster solver, only slightly more difficult to use correctly. O(n log n) in interval number.
  • unsorted
    Marginally slower solver, impossible to misuse. O(n log n) in interval number.