1847. 最近的房间

Hard

题目描述

有一个酒店有 n 个房间。房间由一个二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi、大小为 sizei 的房间。每个 roomIdi 保证是唯一的。

你还有 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej]。第 j 个查询的答案是房间号 id，该房间满足：

房间的大小至少为 minSizej，并且
abs(id - preferredj) 最小化，其中 abs(x) 是 x 的绝对值。

如果绝对差值相等，则使用房间号最小的房间。如果没有这样的房间，答案是 -1。

返回一个长度为 k 的数组 answer，其中 answer[j] 包含第 j 个查询的答案。

示例 1：

输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：
查询 [3,1]：房间号 3 是最近的，因为 abs(3 - 3) = 0，且大小 2 至少为 1。答案是 3。
查询 [3,3]：没有大小至少为 3 的房间，所以答案是 -1。
查询 [5,2]：房间号 3 是最近的，因为 abs(3 - 5) = 2，且大小 2 至少为 2。答案是 3。

示例 2：

输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]

约束：

n == rooms.length
1 <= n <= 10^5
k == queries.length
1 <= k <= 10^4
1 <= roomIdi, preferredj <= 10^7
1 <= sizei, minSizej <= 10^7

解题思路

这是一个典型的离线查询+二分搜索问题。关键思路是：

核心观察： 对于每个查询，我们需要在满足大小要求的房间中找到房间号最接近目标的房间。

解决方案：

离线处理查询：按最小房间大小从大到小排序查询，这样可以逐步添加满足条件的房间
排序房间：按房间大小从大到小排序，便于按顺序处理
维护有序集合：使用有序集合（如 TreeSet）维护当前可用的房间号
二分查找：对每个查询，在有序集合中用二分查找找到最接近的房间号

具体步骤：

将查询按最小大小降序排列，记录原始索引
将房间按大小降序排列
维护一个指针，逐步将满足当前查询大小要求的房间添加到有序集合
对每个查询，在集合中二分查找最接近目标的房间号（需要检查左右两个候选）

时间复杂度优化： 通过离线处理避免了对每个查询都重新筛选房间，总体复杂度为 O((n+k)logn)。

代码实现

class Solution {
public:
    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
        int n = rooms.size(), k = queries.size();
        
        // 给查询添加索引并按最小大小降序排序
        vector<array<int, 3>> indexedQueries;
        for (int i = 0; i < k; i++) {
            indexedQueries.push_back({queries[i][1], queries[i][0], i});
        }
        sort(indexedQueries.begin(), indexedQueries.end(), greater<array<int, 3>>());
        
        // 按房间大小降序排序
        sort(rooms.begin(), rooms.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] > b[1];
        });
        
        vector<int> result(k);
        set<int> availableRooms;
        int roomIdx = 0;
        
        for (const auto& query : indexedQueries) {
            int minSize = query[0], preferred = query[1], queryIdx = query[2];
            
            // 添加所有大小满足要求的房间
            while (roomIdx < n && rooms[roomIdx][1] >= minSize) {
                availableRooms.insert(rooms[roomIdx][0]);
                roomIdx++;
            }
            
            if (availableRooms.empty()) {
                result[queryIdx] = -1;
                continue;
            }
            
            // 在可用房间中找到最接近preferred的房间
            auto it = availableRooms.lower_bound(preferred);
            int closest = -1, minDist = INT_MAX;
            
            // 检查大于等于preferred的房间
            if (it != availableRooms.end()) {
                int dist = abs(*it - preferred);
                if (dist < minDist || (dist == minDist && *it < closest)) {
                    minDist = dist;
                    closest = *it;
                }
            }
            
            // 检查小于preferred的房间
            if (it != availableRooms.begin()) {
                --it;
                int dist = abs(*it - preferred);
                if (dist < minDist || (dist == minDist && *it < closest)) {
                    minDist = dist;
                    closest = *it;
                }
            }
            
            result[queryIdx] = closest;
        }
        
        return result;
    }
};

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        from sortedcontainers import SortedSet
        import bisect
        
        n, k = len(rooms), len(queries)
        
        # 给查询添加索引并按最小大小降序排序
        indexed_queries = []
        for i, (preferred, min_size) in enumerate(queries):
            indexed_queries.append((min_size, preferred, i))
        indexed_queries.sort(reverse=True)
        
        # 按房间大小降序排序
        rooms.sort(key=lambda x: x[1], reverse=True)
        
        result = [0] * k
        available_rooms = SortedSet()
        room_idx = 0
        
        for min_size, preferred, query_idx in indexed_queries:
            # 添加所有大小满足要求的房间
            while room_idx < n and rooms[room_idx][1] >= min_size:
                available_rooms.add(rooms[room_idx][0])
                room_idx += 1
            
            if not available_rooms:
                result[query_idx] = -1
                continue
            
            # 在可用房间中找到最接近preferred的房间
            pos = available_rooms.bisect_left(preferred)
            closest = -1
            min_dist = float('inf')
            
            # 检查大于等于preferred的房间
            if pos < len(available_rooms):
                room = available_rooms[pos]
                dist = abs(room - preferred)
                if dist < min_dist or (dist == min_dist and room < closest):
                    min_dist = dist
                    closest = room
            
            # 检查小于preferred的房间
            if pos > 0:
                room = available_rooms[pos - 1]
                dist = abs(room - preferred)
                if dist < min_dist or (dist == min_dist and room < closest):
                    min_dist = dist
                    closest = room
            
            result[query_idx] = closest
        
        return result

public class Solution {
    public int[] ClosestRoom(int[][] rooms, int[][] queries) {
        int n = rooms.Length, k = queries.Length;
        
        // 给查询添加索引并按最小大小降序排序
        var indexedQueries = new List<(int minSize, int preferred, int index)>();
        for (int i = 0; i < k; i++) {
            indexedQueries.Add((queries[i][1], queries[i][0], i));
        }
        indexedQueries.Sort((a, b) => b.minSize.CompareTo(a.minSize));
        
        // 按房间大小降序排序
        Array.Sort(rooms, (a, b) => b[1].CompareTo(a[1]));
        
        var result = new int[k];
        var availableRooms = new SortedSet<int>();
        int roomIdx = 0;
        
        foreach (var query in indexedQueries) {
            int minSize = query.minSize, preferred = query.preferred, queryIdx = query.index;
            
            // 添加所有大小满足要求的房间
            while (roomIdx < n && rooms[roomIdx][1] >= minSize) {
                availableRooms.Add(rooms[roomIdx][0]);
                roomIdx++;
            }
            
            if (availableRooms.Count == 0) {
                result[queryIdx] = -1;
                continue;
            }
            
            // 在可用房间中找到最接近preferred的房间
            int closest = -1;
            int minDist = int.MaxValue;
            
            // 检查大于等于preferred的房间
            var view = availableRooms.GetViewBetween(preferred, int.MaxValue);
            if (view.Count > 0) {
                int room = view.Min;
                int dist = Math.Abs(room - preferred);
                if (dist < minDist || (dist == minDist && room < closest)) {
                    minDist = dist;
                    closest = room;
                }
            }
            
            // 检查小于preferred的房间
            view = availableRooms.GetViewBetween(int.MinValue, preferred - 1);
            if (view.Count > 0) {
                int room = view.Max;
                int dist = Math.Abs(room - preferred);
                if (dist < minDist || (dist == minDist && room < closest)) {
                    minDist = dist;
                    closest = room;
                }
            }
            
            result[queryIdx] = closest;
        }
        
        return result;
    }
}

var closestRoom = function(rooms, queries) {
    const indexedQueries = queries.map((query, index) => [...query, index]);
    indexedQueries.sort((a, b) => b[1] - a[1]);
    
    rooms.sort((a, b) => b[1] - a[1]);
    
    const result = new Array(queries.length);
    const availableRooms = new Set();
    let roomIndex = 0;
    
    for (const [preferred, minSize, queryIndex] of indexedQueries) {
        while (roomIndex < rooms.length && rooms[roomIndex][1] >= minSize) {
            availableRooms.add(rooms[roomIndex][0]);
            roomIndex++;
        }
        
        if (availableRooms.size === 0) {
            result[queryIndex] = -1;
            continue;
        }
        
        let bestRoom = -1;
        let minDiff = Infinity;
        
        for (const roomId of availableRooms) {
            const diff = Math.abs(roomId - preferred);
            if (diff < minDiff || (diff === minDiff && roomId < bestRoom)) {
                minDiff = diff;
                bestRoom = roomId;
            }
        }
        
        result[queryIndex] = bestRoom;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O((n+k)log n)	排序查询 O(k log k)，排序房间 O(n log n)，处理查询时每次集合操作 O(log n)
空间复杂度	O(n+k)	存储查询索引 O(k)，有序集合最多存储 n 个房间号 O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目