从 Python 中的查询中查找最近房间的程序

• Z时代
• 2024-01-10
• 分类：综合

假设有一个叫做房间的数组。其中，rooms[i] 包含一对 [roomId_i, size_i] 表示一个房间，其 id 为 roomId_i，大小为 size_i。所有房间号都是不同的。我们还有另一个数组查询，其中查询 [j] 包含一对 [preferred_j, minSize_j]。第 j 个查询的答案是一个房间的房间号 id，使得 -

• 房间的大小至少为 minSize_j，并且

• |id - 优选_j| 被最小化。

现在，如果绝对差异有平局，则使用 id 最小的房间。如果没有这样的房间，则返回-1。因此，我们必须找到一个名为 answer 的数组，其长度与查询相同，其中包含第 j 个查询的答案。

因此，如果输入类似于 rooms = [[2,2],[1,2],[3,2]] 查询 = [[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。

示例

让我们看下面的实现来更好地理解

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 中的查询中查找最近房间的程序 的全部内容， 来源链接： utcz.com/z/356690.html