Pythonのクエリから最も近い部屋を見つけるプログラム

部屋と呼ばれる配列があるとします。ここで、rooms [i]にはペア[roomId_i、size_i]が含まれ、IDがroomId_i、サイズがsize_iの部屋を示します。すべての部屋番号は異なります。また、別の配列クエリがあり、querys [j]にはペア[preferred_j、minSize_j]が含まれています。 j番目のクエリに対する答えは、次のような部屋の部屋番号IDです-

• 部屋のサイズは少なくともminSize_jであり、

• | id --preferred_j |最小化されます。

ここで、絶対差に同点がある場合は、IDが最小の部屋を使用します。そのような部屋がない場合は、-1を返します。したがって、j番目のクエリに対する回答を含む、クエリと同じ長さのanswerという配列を見つける必要があります。

したがって、入力が部屋のようである場合=[[2,2]、[1,2]、[3,2]]クエリ=[[3,1]、[3,3]、[5,2]]、

• クエリ[3,1]の場合：| 3-3 |であるため、部屋3が最も近くにあります。 =0で、サイズ2は少なくとも1なので、答えは3です。

• クエリ[3,3]の場合：サイズが3以上の部屋はないため、答えは-1です。

• クエリ[5,2]の場合：| 3-5 |であるため、部屋3が最も近くにあります。 =2で、サイズ2は少なくとも2なので、答えは3です。

これを解決するには、次の手順に従います-

• サイズに基づいて部屋を並べ替えます。サイズが同じ場合は、部屋IDに基づいて並べ替えます

• クエリ=インデックスiのペア（qid、size、i）のリスト、およびクエリのペア（qid、size）

• サイズに基づいてクエリを逆の順序で並べ替えます。サイズが同じ場合は優先に基づいて、両方が同じ場合はインデックスに基づいて

• ans：=クエリのサイズと同じサイズの配列で、-1で埋めます

• X：=新しいリスト

• クエリの各（qid、size、i）について、実行します

  • 部屋と部屋の最後のアイテムのサイズ>=サイズ、実行

    • （idr、p）：=部屋から最後の要素を削除

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