用 Python 编写程序，根据查询结果查找最近的房间
假设有一个名为 rooms 的数组。其中 rooms[i] 包含一对 [roomId_i, size_i]，表示房间的 id 为 roomId_i，大小为 size_i。所有房间号都不同。我们还有另一个数组查询，其中 queries[j] 包含一对 [preferred_j, minSize_j]。第 j 个查询的答案是房间的房间号 id，使得 −
房间的大小至少为 minSize_j，并且
|id - preferred_j| 最小化。
现在，如果绝对差值相同，则使用 id 最小的房间。如果没有这样的房间，则返回 -1。因此，我们必须找到一个名为 answer 的数组，其长度与查询相同，其中包含第 j 个查询的答案。
因此，如果输入为 rooms = [[2,2],[1,2],[3,2]] queries = [[3,1],[3,3],[5,2]]，则输出将为 [3, -1, 3]，因为
对于查询 [3,1]:房间 3 最接近，因为 |3 - 3| = 0，并且其大小 2 至少为 1，因此答案为 3。
对于查询 [3,3]:没有大小至少为 3 的房间，因此答案为 -1。
对于查询 [5,2]:房间 3 最接近，因为 |3 - 5| = 2，并且其大小 2 至少为 2，因此答案为 3。
为了解决这个问题，我们将遵循以下步骤 −
根据大小对房间进行排序，如果大小相同，则基于房间 ID
queries = 索引 i 的对 (qid,size,i) 列表，以及查询中的对 (qid, size)
根据大小反向对查询进行排序，如果大小相同，则基于首选，如果两者相同，则基于索引
ans := 大小与查询大小相同的数组，并用 -1 填充
X := 一个新列表
对于查询中的每个 (qid, size, i)，执行
当 rooms 和 rooms 最后一个元素的大小 >= size 时，执行
(idr, p) := 从 rooms 中删除最后一个元素
插入 idr 后对 X 进行排序
如果 X 不为空，则
j := 插入 qid 以保持 X 排序的索引
如果 j 与 X 的大小相同，则
ans[i] := X 的最后一个元素
否则，当 j 与 0 相同时，则
ans[i] := X[0]
否则，
如果 X[j] - qid < qid - X[j-1]，则
ans[i] := X[j]
否则，
ans[i] := X[j-1]
返回 ans
示例
让我们看看下面的实现以便更好地理解
import bisect
def solve(rooms, queries):
rooms.sort(key = lambda x: (x[1], x[0]))
queries = [(qid,size,i) for i, (qid, size) in enumerate(queries)]
queries.sort(key = lambda x: (x[1], x[0], x[2]), reverse = True)
ans = [-1] * len(queries)
X = []
for qid, size, i in queries:
while rooms and rooms[-1][1] >= size:
idr, _ = rooms.pop()
bisect.insort(X, idr)
if X:
j = bisect.bisect(X, qid)
if j == len(X):
ans[i] = X[-1]
elif j == 0:
ans[i] = X[0]
else:
if X[j] - qid < qid - X[j-1]:
ans[i] = X[j]
else:
ans[i] = X[j-1]
return ans
rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))
输入
[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]
输出
[3, -1, 3]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
