Python程序：计算完全包含在其他区间内的区间数量

假设我们有一列区间。在这个列表中，interval[i] 包含 [start, end] 值。我们必须找到被另一个区间包含的区间数量。如果一个区间被多个其他区间包含，则只应计算一次。当 s0 ≤ s1 且 e0 ≥ e1 时，区间 [s0, e0] 位于另一个区间 [s1, e1] 内。

因此，如果输入类似于 intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]，则输出将为 2，因为 [3, 4] 和 [5, 5] 分别位于 [2, 6] 和 [4, 7] 内。

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

  • 如果 intervals 列表为空，则
    • 返回 0
  • 根据开始时间对 intervals 列表进行排序，当开始时间相同时，按结束时间的降序排列
  • end_mx := -∞
  • ans := 0
  • 对于 intervals 中的每个 (start, end) 对，执行以下操作：
    • 如果 end <= end_mx，则
      • ans := ans + 1
    • end_mx := end_mx 和 end 的最大值
  • 返回 ans

示例

让我们看看下面的实现，以便更好地理解：

def solve(intervals):
   if not intervals:
      return 0

   intervals.sort(key=lambda x: (x[0], -x[1]))

   end_mx = float("-inf")
   ans = 0

   for start, end in intervals:
      if end <= end_mx:
         ans += 1

      end_mx = max(end_mx, end)

   return ans

intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals))

输入

[[2, 6],[3, 4],[4, 7],[5, 5]]

输出

2

更新于：2021年10月18日

438 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告