Pythonの間隔のリストから最長の間隔の長さを見つけるプログラム

各間隔が[start、end]の形式である間隔のリストがあるとします。重なり合う間隔をいくつでもマージして、作成できる最長の間隔を見つける必要があります。

したがって、入力が[[1、6]、[4、9]、[5、6]、[11、14]、[16、20]]の場合、マージ後の出力は9になります。長さ9の区間[1、9]があります。

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

• リスト間隔を並べ替える
• union：=間隔リストの最初の間隔
• best：=union [end] --union [start] + 1
• 最初の時刻を除く間隔で開始時刻sと終了時刻eごとに、
  を実行します。
  • s <=union [end]の場合、
    • union [end]：=union[end]とeの最大値
  • それ以外の場合、
    • union：=新しい間隔[s、e]
  • best：=bestとunion[end]の最大値-union[start] + 1
• ベストリターン

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

例

class Solution:
   def solve(self, intervals):
      intervals.sort()
      union = intervals[0]
      best = union[1] - union[0] + 1
      for s, e in intervals[1:]:
         if s <= union[1]:
            union[1] = max(union[1], e)
         else:
            union = [s, e]
            best = max(best, union[1] - union[0] + 1)
      return best
ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

入力

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

出力

9