Python程序：根据时间区间查找可以选修的最大课程数

假设我们有一系列区间，格式为[开始时间, 结束时间]，表示课程的开始和结束时间。我们必须找到可以选修的最大课程数，假设我们一次只能选修一门课程，并且一门课程的开始时间必须晚于上一门课程的结束时间。

因此，如果输入类似于 times = [[3, 6],[6, 9],[7, 8],[9, 11]]，则输出为 3，因为我们可以选修课程 [[3, 6], [7, 8], [9, 11]]

为了解决这个问题，我们将遵循以下步骤：

  • 根据结束时间排序课程

  • 计数器 := 0，结束时间 := -1

  • 对于 i 从 0 到 times 的大小，执行：

    • 如果 times[i, 0] > end 为真，则

      • 计数器 := 计数器 + 1

      • 结束时间 := times[i, 1]

  • 返回计数器

让我们看看下面的实现来更好地理解。

示例

 在线演示

class Solution:
   def solve(self, times):
      times.sort(key=lambda x: x[1])

      counter = 0
      end = -1

      for i in range(len(times)):
         if times[i][0] > end:
            counter += 1
            end = times[i][1]
      return counter

ob = Solution()
times = [
   [3, 6],
   [6, 9],
   [7, 8],
   [9, 11]
]
print(ob.solve(times))

输入

[ [3, 6],[6, 9],[7, 8],[9, 11]]

输出

3

更新于：2020年11月10日

189 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告