Pythonですべての映画を上映するために必要な映画館の最小数を見つけるためのプログラム

さまざまな映画の上映の間隔のリストがあるとすると（それらは重複する可能性があります）、すべての映画を上映できるようにするために必要な劇場の最小数を見つける必要があります。

したがって、入力がintervals =[[20、65]、[0、40]、[50、140]]のような場合、[20、65]と[0、40]が重なっているため、出力は2になります。 。 [20、65]と[50、140]も重複していますが、[0、40]と[50、140]は重複していません。したがって、2つの劇場が必要です。

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

• t：=新しいリスト
• 間隔[a、b]ごとに、間隔を指定して
  • tの最後に[a、1]を挿入します
  • tの最後に[b、-1]を挿入します
• ans：=0、count：=0
• ソートされた形式のtの各ペア（x、d）について、
  • count：=count + d
  • ans：=ansとカウントの最大値
• 回答を返す

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

サンプルコード

class Solution:
   def solve(self, intervals):
      t = []
      for a, b in intervals:
         t.append((a, 1))
         t.append((b, -1))
         ans = count = 0
         for x, d in sorted(t):
            count += d
            ans = max(ans, count)
         return ans

ob = Solution()
intervals = [[20, 65],[0, 40],[50, 140]]
print(ob.solve(intervals))

入力

[[20, 65],[0, 40],[50, 140]]

出力

2