Pythonで各クエリを含めるための最小間隔を見つけるプログラム

区間のリストがあるとします。ここで、intervals [i]にはペア（left_i、right_i）があり、left_iで始まりright_i（両方を含む）で終わるi番目の区間を表します。クエリと呼ばれる別の配列もあります。 j番目のクエリに対する答えは、left_i<=クエリ[j]<=right_iとなる最小区間iのサイズです。そのような間隔が見つからない場合は、-1を返します。クエリへの回答を含む配列を見つける必要があります。

したがって、入力がintervals =[[2,5]、[3,5]、[4,7]、[5,5]]クエリ=[3,4,5,6]のような場合、出力はクエリは次のように処理されるため、[3、3、1、4]になります-

• クエリ=3の場合：間隔[3,5]は、3を保持する最小のものです。したがって、5-3 + 1=3です。

• クエリ=4の場合：間隔[3,5]は、4を保持する最小のものです。したがって、5-3 + 1=3です。

• クエリ=5の場合：間隔[5,5]は、5を保持する最小のものです。したがって、5-5 + 1=1です。

• クエリ=6の場合：間隔[4,7]は、6を保持する最小のものです。したがって、7-4 +1=4です。

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

• 間隔：=リストの間隔を逆の順序で並べ替えます

• h：=新しいリスト

• res：=新しいマップ

• ソートされたクエリリストのqごとに、次のようにします

  • 間隔が空ではなく、最後の間隔の終了時刻<=q、do

    • （i、j）：=間隔の最後の間隔、およびそれを削除します

    • j> =qの場合、

      • ペア（j-i + 1、j）をヒープhに挿入します

  • hが空ではなく、h の最上位区間の終了時刻

    • hから最上位の要素を削除する

  • res [q]：=hが空でない場合は、hの最上位間隔の開始時刻。それ以外の場合は-1

• クエリ内のすべてのqのres[q]のリストを返します

例

理解を深めるために、次の実装を見てみましょう

import heapq
def solve(intervals, queries):
   intervals = sorted(intervals)[::-1]
   h = []
   res = {}
   for q in sorted(queries):
      while intervals and intervals[-1][0] <= q:
         i, j = intervals.pop()
         if j >= q:
            heapq.heappush(h, [j - i + 1, j])
      while h and h[0][1] < q:
         heapq.heappop(h)
      res[q] = h[0][0] if h else -1
   return [res[q] for q in queries]

intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries))

入力

[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]

出力

[3, 3, 1, 4]