1 unstable release
0.1.0 | Apr 11, 2022 |
---|
#1544 in Algorithms
19KB
180 lines
w_inter
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
}
License: MIT