Pythonで作業されているタスクの数を見つけるプログラム

各間隔が[start、end）のような間隔のリストがあり、typesと呼ばれる文字列のリストもあるとします。ここで、特定のiについて、intervals [i]は、誰かが[start、end）からジョブタイプ[i]に取り組んだ時間を示します。同じタイプの2つの間隔が重なったり、接触したりすることはありません。したがって、各項目に[start、end、num_types]があり、最初から最後まで、作業中のタスクのnum_types数を示すソートされたマージリストを見つける必要があります。

したがって、入力がintervals =[[0、3]、[5、7]、[0、7]] types =["問題解決"、 "ニュース"、 "ゲームプレイ"]のような場合、出力は次のようになります。 [[0、3、2]、[3、5、1]、[5、7、2]]である必要があります。これは、次のいくつかのタイプの作業が行われているためです。[0、3）「問題解決」と「 「ゲームプレイ」、[3、5）「ゲームプレイ」の間、および[5、7）「ニュース」と「ゲームプレイ」の間。

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

• ev：=新しいリスト

• 間隔内の各間隔の開始と終了のペア（s、e）について、実行します

  • evの最後に（s、1）を挿入します

  • evの最後に（e、-1）を挿入します

• リストを並べ替えるev

• cnt：=0、最後：=-1

• ans：=新しいリスト

• evのイベント（t、inc）の時間と増分パラメータごとに、実行します

  • tがlastと同じでなく、cntが0と同じでない場合、

    • cnt：=cnt + inc

  • 最後：=t

• ansを返す

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

例

class Solution:
   def solve(self, intervals, jobs):
      ev = []
      for s, e in intervals:
         ev.append((s, 1))
         ev.append((e, −1))
      ev.sort()
      cnt = 0
      last = −1
      ans = []
      for t, inc in ev:
         if t != last and cnt != 0:
            ans.append([last, t, cnt])
         cnt += inc
         last = t
      return ans
ob = Solution()
intervals = [
   [0, 3],
   [5, 7],
   [0, 7]
]
types = ["problem solving", "news", "game play"]
print(ob.solve(intervals, types))

入力

[[0, 3],[5, 7],[0, 7]], ["problem solving", "news", "game play"]

出力

[[0, 3, 2], [3, 5, 1], [5, 7, 2]]