Python程式：查詢每個區間內完成的任務數量

假設我們有一個區間列表，每個區間都類似於[開始，結束)，我們還有一個名為型別的字串列表。現在，對於給定的i，intervals[i]顯示某人在[開始，結束)時間段內完成job types[i]的工作。相同型別的兩個區間絕不會重疊或接觸。因此，我們必須找到一個排序的合併列表，其中每個專案都有[開始，結束，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 := 一個新的列表

  • 對於intervals中的每個區間開始結束對(s, e)，執行：

    • 在ev的末尾插入(s, 1)

    • 在ev的末尾插入(e, -1)

  • 對列表ev進行排序

  • cnt := 0, last := -1

  • ans := 一個新的列表

  • 對於ev中的每個時間和增量引數(t, inc)，執行：

    • 如果t與last不同且cnt與0不同，則

      • cnt := cnt + inc

    • last := 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]]

更新於：2020年10月21日

73 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.