Interval / Range Index (Rust)
Topics: intervals, binary search, ordered index, overlap queries
Problem
Index a set of half-open intervals [start, end) and answer two queries: which intervals contain
a point (stabbing), and which overlap a query range (overlapping). This is the workhorse
behind booking/calendar conflict checks, IP-range lookups, and time-range filters.
pub struct IntervalIndex { /* … */ }
impl IntervalIndex {
pub fn new() -> Self;
pub fn add(&mut self, start: i32, end: i32, label: &str); // [start, end)
pub fn stabbing(&self, point: i32) -> Vec<Interval>; // start <= point < end
pub fn overlapping(&self, lo: i32, hi: i32) -> Vec<Interval>; // overlaps [lo, hi)
}
- Keep intervals sorted by start (ties keep insertion order).
stabbing(p) → intervals with start <= p < end, in start order.overlapping(lo, hi) → intervals where start < hi && end > lo (half-open overlap), in start
order.
add [0,5)=a, [10,20)=b, [15,30)=c, [0,100)=wide
stabbing(16) → [wide, b, c]
overlapping(12,18) → [wide, b, c]
overlapping(5,7) → [right] only // a touching [..,5) is excluded (end exclusive)
Key concepts
- Sort by start, binary-search the cut: every candidate has
start < hi (overlap) or
start <= point (stabbing) — Vec::partition_point finds that prefix in O(log n).
- Filter by end: within the prefix, keep intervals whose
end clears the lower bound. Half-open
means a touching boundary (end == lo) does not overlap.
The Interval type, the index, and new are provided; you implement add, stabbing, and
overlapping.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.