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

假设有一个名为rooms的数组。其中rooms[i]包含一个配对[roomId_i, size_i]，表示其id为roomId_i，大小为size_i的房间。所有房间号都是不同的。我们还有另一个名为queries的数组，其中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，并且它的大小至少为1，因此答案是3。

• 对于查询[3,3]：没有大小至少为3的房间，因此答案为-1。

• 对于查询[5,2]：房间3是最接近的，因为|3-5|=2，并且它的大小至少为2，因此答案是3。

要解决这个问题，我们将按照以下步骤进行−

• 基于size对rooms进行排序，如果size相同，则根据room id排序

• 从索引中创建一个名为queries列表的对（qid，大小，i），并在queries中创建一个对（qid，大小）

• 基于大小对查询进行反向排序，如果大小相同，则根据首选项排序，当两者相同时，则根据索引排序

• ans：具有与查询相同大小的数组，并用-1填充

• X：一个新列表

• 对于每个（qid，大小，i）在查询中，进行以下操作

  • 当房间不为空且rooms的最后一个项目的大小>=size时，请执行以下操作
    • idr，p :=从rooms删除最后一个元素

    • 插入idr后将X排序

  • 如果X不为空，则

    • j：在保持X排序的位置插入qid的索引

    • 如果j与X的大小相同，则

    • ans [i]：X的最后一个元素

    • 否则当j与0相同时，则

    • ans [i]：X [0]

    • 否则，

    • 如果X [j] -qid

      • 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]