Step 4 of 6

Range queries with BTreeMap and BTreeSet

You met BTreeMap and BTreeSet in the hashmaps module as the maps that keep their keys sorted. Sorted iteration is nice, but their real superpower is range queries: questions about keys between two values, answered without looking at the rest.

A BTreeMap is a balanced tree, so finding where a range starts is O(log n), and walking k entries from there costs O(k). Compare that with a HashMap, where you'd have to look at every key.

use std::collections::BTreeMap;

fn main() {
    // minute of the day -> temperature
    let mut temps: BTreeMap<u32, f64> = BTreeMap::new();
    temps.insert(600, 14.5); // 10:00
    temps.insert(615, 15.0);
    temps.insert(540, 12.0); // 09:00
    temps.insert(660, 16.5);
    temps.insert(720, 18.0);

    for (minute, t) in temps.range(600..700) {
        println!("{:02}:{:02} {t}", minute / 60, minute % 60);
    }
    println!("first: {:?}", temps.first_key_value());
    println!("at or before 650: {:?}", temps.range(..=650).next_back());
    println!("at or after 650: {:?}", temps.range(650..).next());
    println!("readings before 10:00: {}", temps.range(..600).count());
}

10:00 14.5
10:15 15
11:00 16.5
first: Some((540, 12.0))
at or before 650: Some((615, 15.0))
at or after 650: Some((660, 16.5))
readings before 10:00: 1

next_back() takes an item from the end of a double-ended iterator, so on a range it gives the largest key in that range without walking through the others. BTreeSet has the same methods (range, first, last, pop_first, pop_last).

HashMap or BTreeMap?

Pick BTreeMap when you need order: time series, price levels, leaderboards, schedules, or simply output that has to be deterministic.

Common mistakes

• range(..=x).next() for a floor query. That's the smallest key in the range. The floor is the last one: next_back().
• A backwards range. map.range(10..5) panics with range start is greater than range end in BTreeMap. Check your bounds when they come from input.
• Filtering the whole map. map.iter().filter(|(k, _)| **k >= a && **k < b) gives the same entries as map.range(a..b) but costs O(n) instead of O(log n + k).

Your task

A meeting room booking system. Write a Calendar with:

• fn new() -> Self
• fn book(&mut self, start: u32, end: u32) -> bool that books the half-open time slot start..end and returns true, or returns false (and books nothing) if it overlaps an existing booking or if start >= end

Half-open means 9..10 and 10..11 don't overlap. Store bookings as a BTreeMap<u32, u32> from start to end. The tests make 100,000 bookings, so checking every existing booking is too slow. You only need to look at one: the booking with the latest start before end (range(..end).next_back()). If it ends after start, the new slot overlaps.

Challenge 2

A shop keeps the history of a product's price as a BTreeMap<u32, u32> from the time a price was set to the new price (in cents). The price at any moment is the one set most recently at or before that moment.

Write fn price_at(history: &BTreeMap<u32, u32>, time: u32) -> Option<u32> (None before the first price was ever set) and fn changes_between(history: &BTreeMap<u32, u32>, from: u32, to: u32) -> usize that counts the price changes with from <= time <= to (0 when from > to). The tests ask 200,000 questions about a long history, so use range for both.

Challenge 3

A hotel front desk wants the free room whose number is closest to the one a guest asks for (some guests want to be near friends). Write fn nearest_room(free: &BTreeSet<u32>, wanted: u32) -> Option<u32>: return the free room with the smallest distance to wanted; on a tie, the lower number. None if no room is free.

Look at just two candidates: the floor (largest free room <= wanted) and the ceiling (smallest free room >= wanted). The tests make 100,000 requests against 100,000 rooms, so don't scan the set.

Previous: Priority queues with BinaryHeap Next: LinkedList, and why it's rare