Closest room

Array Binary Search Sorting Ordered Set

41.1% acceptance

Feb 25, 2026

537

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei] denotes that there is a room with room number roomIdi and size equal to sizei. You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth query is the room number id of a room such that: The room has a size of at least minSizej, and abs(id - preferredj) is minimized. If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1. Return an array answer of length k where answer[j] contains the answer to the jth query.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::BTreeSet;

impl Solution {
  pub fn closest_room(mut rooms: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    // Sort rooms by size descending
    rooms.sort_unstable_by(|a, b| b[1].cmp(&a[1]));

    let k = queries.len();
    // Sort query indices by minSize descending
    let mut order: Vec<usize> = (0..k).collect();
    order.sort_unstable_by(|&a, &b| queries[b][1].cmp(&queries[a][1]));

    let mut answer = vec![-1i32; k];
    let mut available: BTreeSet<i32> = BTreeSet::new();
    let mut room_idx = 0usize;

    for qi in order {
      let preferred = queries[qi][0];
      let min_size = queries[qi][1];

      // Add all rooms with size >= min_size
      while room_idx < rooms.len() && rooms[room_idx][1] >= min_size {
        available.insert(rooms[room_idx][0]);
        room_idx += 1;
      }

      if available.is_empty() {
        continue;
      }

      let mut best = -1i32;
      let mut best_diff = i32::MAX;

      // Largest id <= preferred
      if let Some(&id) = available.range(..=preferred).next_back() {
        let diff = preferred - id;
        if diff < best_diff || (diff == best_diff && id < best) {
          best = id;
          best_diff = diff;
        }
      }
      // Smallest id > preferred
      if let Some(&id) = available.range(preferred + 1..).next() {
        let diff = id - preferred;
        if diff < best_diff || (diff == best_diff && id < best) {
          best = id;
        }
      }

      answer[qi] = best;
    }

    answer
  }
}