Pythonの他の間隔内に完全に含まれている間隔の数をカウントするプログラム

間隔のリストがあるとします。このリストでは、interval [i]には[start、end]の値があります。間隔の数が別の間隔に含まれていることを確認する必要があります。 1回だけカウントする必要がある他の複数の間隔に含まれる間隔がある場合。区間[s0、e0]は、s0≤s1かつe0≥e1の場合、別の区間[s1、e1]の内側にあります。

したがって、入力がintervals =[[2、6]、[3、4]、[4、7]、[5、5]]のような場合、[3、4]と[ 5、5]はそれぞれ[2、6]と[4、7]の中にあります。

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

• 間隔リストが空の場合、
  • 0を返す
• 開始時刻に基づいて間隔リストを並べ替えます。開始時刻が同じ場合は、終了時刻の降順で並べ替えます
• end_mx：=-infinity
• ans：=0
• 間隔を置いて（開始、終了）ペアごとに、
  • end <=end_mxの場合、
    • ans：=ans + 1
  • end_mx：=end_mxとendの最大値
• 回答を返す

例

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

def solve(intervals):
   if not intervals:
      return 0

   intervals.sort(key=lambda x: (x[0], -x[1]))

   end_mx = float("-inf")
   ans = 0

   for start, end in intervals:
      if end <= end_mx:
         ans += 1

      end_mx = max(end_mx, end)

   return ans

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

入力

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

出力

2