[Rust] Offline Queries
Intuition\n Describe your first thoughts on how to solve this problem. \nWhen approaching a problem of the form "Given this data, answer these queries", there a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWhen approaching a problem of the form "Given this data, answer these queries", there are two natural ways to approach it. First, you could create a data structure (often a segment tree) which allows for efficient querying, amortising the cost of building the data structure across all of the queries. This works well in many cases, and its initially what I went with for this question, although sometimes the data structure can be complicated and error-prone, which is what I found here.\n\nAnother approach is **offline queries**. Rather than changing our representation of the data alone to answer arbitrary queries, we can recognise that *we already know all of the queries we will be performing*. By changing our representation of the queries, often as simple as sorting them, we can answer them in an ideal order, then re-order our answers back into the original order of the queries. \n\nOffline queries often leads to simpler and more efficient algorithms - a poorly built (aka self-implemented) data structure could maintain good time complexities, but struggle with real-world efficiency due to excessive heap allocations or cache misses. I find custom-data-structure based solutions more intuitive, but I think its worthwhile re-evaluating other alternatives when they come up. (Another common segtree alternative is a custom mergesort). \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe first step is to sort the queries and rooms vectors by size. I\'ve also converted them into custom structs, which are easier easier to understand and reduce memory indirection. I also initialise an empty set of available rooms. Note that we keep track of each query\'s initial index.\n\nNow, the queries can be answered in order from the largest required size to the smallest. Every new query will accept all the rooms available to the previous query, plus some extra, so the first step is adding the newly available rooms to the set. Then, check the first room available before and after the preferred id, and check which one (if any) to take.\n\nAfterwards, re-order the answer vector by the query indices to re-create the original query order, and return the vector.\n\n# Complexity\nLet `r = rooms.len()` and `q = queries.len()`.\n- Time complexity: $$O(r \\log(r) + q\\log(q)+q*B\\log(r))$$\n    - $$O(r \\log(r) + q\\log(q))$$ for sorting.\n    - $$O(B\\log(r))$$ lookup time for each query.\n    - Note that Rust\'s standard library uses a B Tree rather than a standard Binary Search Tree to represent an ordered set. This means lookups involve linear searching, more comparisons in exchange for better cache efficiency. Currently, `B = 6`.\n- Space complexity: $$O(r + q)$$\n\n# Code\n```\nuse std::collections::BTreeSet;\n\nstruct Query {\n    ideal: i32,\n    size: i32,\n    index: usize,\n}\n\nstruct Room {\n    id: i32,\n    size: i32\n}\n\nimpl Solution {\n    pub fn closest_room(rooms: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {\n        let mut queries: Vec<Query> = queries\n            .into_iter()\n            .enumerate()\n            .map(|(index, query)| Query { ideal: query[0], size: query[1], index })\n            .collect();\n        let mut rooms: Vec<Room> = rooms\n            .into_iter()\n            .map(|r| Room { id: r[0], size: r[1] })\n            .collect();\n        queries.sort_unstable_by_key(|query| query.size);\n        rooms.sort_unstable_by_key(|room| room.size);\n        let mut available_rooms = BTreeSet::new();\n\n        let mut ans = queries.into_iter().rev().map(|query| {\n            while let Some(room) = rooms.pop() {\n                if room.size < query.size {\n                    rooms.push(room);\n                    break;\n                } else {\n                    available_rooms.insert(room.id);\n                }\n            }\n            let lower = available_rooms.range(..query.ideal).next_back().copied();\n            let upper = available_rooms.range(query.ideal..).next().copied();\n            let room = match (lower, upper) {\n                (None, None) => -1,\n                (Some(x), None) => x,\n                (None, Some(y)) => y,\n                (Some(x), Some(y)) => \n                    if query.ideal - x > y - query.ideal { y } else { x },\n            };\n            (room, query.index)\n        }).collect::<Vec<_>>();\n        ans.sort_unstable_by_key(|(_, id)| *id);\n        ans.into_iter().map(|(a, _)| a).collect()\n    }\n}\n```
['Array', 'Sorting', 'Iterator', 'Enumeration', 'Ordered Set', 'Rust']