Interval / Range Index (Go)
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.
func New() *IntervalIndex
func (x *IntervalIndex) Add(start, end int, label string) // [start, end)
func (x *IntervalIndex) Stabbing(point int) []Interval // start <= point < end
func (x *IntervalIndex) Overlapping(lo, hi int) []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 (for overlap) or
start <= point (for stabbing) — a sort.Search 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.
Run
go test -v ./challenges/interval-index/go/
Sign in to submit your solution.