用 Python 编写程序来计算完全包含在其他间隔内的间隔数

pythonserver side programmingprogramming更新于 2026/1/18 11:56:17

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

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

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

如果 intervals 列表为空，则
- 返回 0
根据开始时间对 intervals 列表进行排序，当开始时间相同时，按结束时间的降序排序
end_mx := -infinity
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))