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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告