Pythonでターゲット間隔をマージして間隔を見つけるプログラム

重複しない間隔のリストがあるとします。これらは終了時間に基づいてソートされます。別の間隔ターゲットがあります。間隔が重複せず、並べ替えられるように、ターゲットをマージした後の最終間隔を見つけます。

したがって、入力がintervals =[[1、15]、[25、35]、[75、90]]、target =[10、30]のような場合、出力は[[1、35]、[ 75、90]]最初の2つの間隔[1、15]と[25、35]がマージされます。

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

• ivの最後にターゲットを挿入

• 開始時間に基づいてivを並べ替える

• res：=最初の間隔の新しいリスト

• i：=1

• i

  • iv[i]の開始時刻<=resの最後の間隔の終了時刻の場合

    • resの最後の間隔の終了時間=（resの最後の間隔の終了時間とiv [i]の終了時間）の最大値

  • それ以外の場合

    • resの最後にiv[i]を挿入します

  • i：=i + 1

• 解像度を返す

例（Python）

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

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

入力

[[1, 15],[25, 35],[75, 90]], [10, 30]

出力

[[1, 35], [75, 90]]