0

如何找到落在给定范围内的间隔数。例如让我解释这个问题假设有 Range [1,10] 并且提供的间隔是 (1,3),(1,8),(2,4),(2,5),(2,3) ,(3,9),(3,8),(3,6) 并要求找出落在范围 [1,5] 之间的区间数，答案是 4。这些是四个 [(1 ,3),(2,4),(2,5),(2,3)] 区间在 [1,5] 范围内。就像有 Range[1,N] 并且我为您提供间隔一样，那么如何找出给定范围内有多少间隔。对于每个查询，此任务的最佳复杂性是多少？

4

1 回答 1

2

上）。你不能做得更好。至少，您必须回答每个间隔都对查询有效，即 O(n)。您可以通过简单地遍历列表来测试 query_min <= interval_min && query_max <= interval_max 来获得 O(n)

于 2013-08-08T02:23:06.653 回答