英文:
Find an amount of subintervals containing an interval from a given set
问题
A closed interval [a, b] and a set S of its closed subintervals [l_i, r_i], i = 1..n, are given.
考虑一个由[a, b]的闭区间组成的集合C，使得每个C中的闭区间[c_j, d_j]都至少包含S中的一个区间，例如对于每个j = 1..m，存在i使得c_j <= l_i <= r_i <= d_j。
找到m = |C|，即C中的项数。
这里的所有数字都是非负整数。
一个明显的解决方案是遍历每一个可能的子区间，这本身需要O(l^2)的时间，其中l = b - a，然后对于每个子区间，我们遍历S并检查它是否包含[l_i, r_i]中的任何一个区间，这需要O(n)的时间。
因此，结果的复杂度将是O(l^2*n)，因此如果l和n成比例，这将导致立方复杂度。我想知道是否可以得出更快的解决方案。
英文:
A closed interval [a, b] and a set S of it's closed subintervals [l_i, r_i], i = 1..n, are given.
Consider a set C of [a, b]'s closed subintervals such that each [c_j, d_j] from C non-strictly contains (at least one) interval from S, e. g. for each j = 1..m exists i such c_j <= l_i <= r_i <= d_j.
Find m = |C|, e. g. an amount of items in C.
All numbers here are nonnegative integers.
An obvious solution would be to iterate through every single possible subinterval, witch itself takes O(l^2) time, where l = b - a, and then for each subinterval we iterate through S and check if it contains any of [l_i, r_i]'s, witch would take O(n).
So resulting complexity would be O(l^2*n), so if l and n are proportional, this results in a qubic complexity. I wounder if faster solution can be derived.
答案1
得分: 2
解析 S，构建一个映射：left_to_right，其中键是 S 的左端点，值是相关的右端点。如果相同的左端点重复出现，则存储最小的相关右端点。
例如，
假设我们的范围是 [1, 20]，S = {[3,7], [5,10], [15,17]}
left_to_right = {3 => 7, 5 => 10, 15 => 17}
count = 0 # 我们最终将返回的范围计数
然后，以降序解析 left_to_right 的键。
解析 15:
count += 15 * (20 - 17 + 1) # 因为左侧的每个 1-15 都可以与右侧的 17-20 中的每个配对，以包含此区间
存储最小已使用的右端点为 17
解析 5:
count += 5 * (16 - 10 + 1) # 因为左侧的每个 1-5 都可以与右侧的 10-16 中的每个配对；右侧的 17+ 已经计数。
存储最小已使用的右端点为 10
解析 3:
count += 3 * (9 - 7 + 1) # 因为左侧的每个 1-3 都可以与右侧的 7-9 中的每个配对，右侧的 10+ 已经计数。
在这个示例中，我们计算包含 [15, 17]、然后包含 [5, 10] 但不包含 [15, 17]、最后包含 [3, 7] 但不包含 [5, 10]（或 [15, 17]）的区间数量。
英文:
Sketch of how to do this:
Parse S, building a map: left_to_right, which has as keys the left endpoints of S, and as values the associated right endpoints. If the same left endpoint is repeated, store the smallest associated right endpoint.
E.g.,
say our range is [1, 20], and S = {[3,7], [5,10], [15,17]}
left_to_right = {3 => 7, 5 => 10, 15 => 17}
count = 0 # count of ranges that we'll eventually return
We then parse the keys of left_to_right in descending order.
parse 15:
count += 15 * (20 - 17 + 1) # because each of 1-15 on the left can be paired with each of 17-20 on the right to include this interval
store smallest_right_used = 17
parse 5:
count += 5 * (16 - 10 + 1) # because each of 1-5 on the left can be paired with each of 10-16 on the right; 17+ on the right have already been counted.
store smallest_right_used = 10
parse 3:
count += 3 * (9 - 7 + 1) # because each of 1-3 on the left can be paired with each of 7-9 on the right, and 10+ on the right have already been counted.
In the example, we count the number of intervals containing [15, 17], then the number of intervals containing [5, 10] but not [15, 17], then the number of intervals containing [3, 7] but not [5, 10] (or [15, 17]).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论