w_inter/lib.rs
1//! A pair of solvers for the [Weighted Interval Scheduling Problem](https://en.wikipedia.org/wiki/Interval_scheduling).
2//!
3//! #### Features
4//! - Zero external dependencies, although requires an allocator (not optional yet).
5//! - Flexible: anything implementing `Ord + Add + Clone` may be thought of as an interval bound or a weight type.
6//! - Efficient: running in `O(n log n)`.
7//! - Fast: cache-aware, zero-reallocation APIs are available.
8//!
9//! #### Simple Example
10//! ```text
11//! 3───────────┐
12//! └───────────┘
13//! 8───────────────────┐
14//! └───────────────────┘
15//! 5───────────┐ 7───────────────┐
16//! └───────────┘ └───────────────┘
17//! 3───────────────────────┐ 4───────────┐
18//! └───────────────────────┘ └───────────┘
19//! 2───┐ 5───────┐ 3───────────────┐
20//! └───┘ └───────┘ └───────────────┘
21//! ◀──0───1───2───3───4───5───6───7───8───9───10──11──▶
22//! ```
23//! ```rust
24//! let intervals = vec![
25//! (0u8, 1u8, 2u8).into(), // (start, end, weight)
26//! (0u8, 6u8, 3u8).into(),
27//! (1u8, 4u8, 5u8).into(),
28//! (3u8, 5u8, 5u8).into(),
29//! (3u8, 8u8, 8u8).into(),
30//! (4u8, 7u8, 3u8).into(),
31//! (5u8, 9u8, 7u8).into(),
32//! (6u8, 10u8, 3u8).into(),
33//! (8u8, 11u8, 4u8).into()
34//! ];
35//!
36//! let optimal = unsorted(&intervals);
37//!
38//! assert_eq!(
39//! optimal,
40//! vec![
41//! (1u8, 4u8, 5u8).into(),
42//! (5u8, 9u8, 7u8).into()
43//! ]
44//! );
45//! ```
46//!
47//! #### Fast (Amortized Allocation) Example
48//!
49//! ```rust
50//! // our goal is to allocate once and reuse the same buffers
51//! // measure (or apply a guess) to avoid having to resize the vector.
52//! let max_interval_count = problems.iter().map(|i| i.len()).max();
53//!
54//! // we can say with certainty that the memo buffer
55//! // will never need to be larger than the largest input size.
56//! let mut memo = vec![0u8; max_interval_count];
57//!
58//! // we don't know how big the solution set will be,
59//! // but it can't be larger than the largest input size.
60//! let mut soln = Vec::with_capacity(max_interval_count);
61//!
62//! for intervals in problems {
63//! // perhaps we know our intervals to be *almost* sorted,
64//! // so we choose to use an algorithm tuned for this case.
65//! sort(&mut intervals);
66//!
67//! // we don't strictly need to, but we clear the old solution set,
68//! // so that only the optimal set from this run ends up in the buffer.
69//! soln.clear();
70//!
71//! sorted(
72//! &intervals,
73//! &mut memo,
74//! &mut soln
75//! );
76//!
77//! // we can now use the `soln` buffer before it's recycled
78//! }
79//! ```
80//!
81
82mod traits;
83mod util;
84mod weighted_interval;
85mod solvers;
86
87pub use solvers::{sorted, unsorted}; // expose solver functions
88pub use weighted_interval::WeightedInterval; // expose default weighted interval struct
89pub use traits::{Interval, Weighted}; // expose traits so users can implement them on their own types