具有公共交集的最大范围数

Question

我遇到了问题，我需要找到最多数量的具有公共交集的范围。但是我找不到任何好的解决方案。

如果我们有这些范围：

<0, 4>

<2, 6>

<4, 6>

所以在这种情况下，所有集合都有一个公共交集，它是

<4, 4>

有没有办法在 C++ 中找到它？

Answer 1

1. 创建保存坐标的结构，它是范围的开始或结束。
2. 创建结构的数组（向量）并让它保存输入范围的所有开始和结束。
3. 按坐标的升序对数组进行排序。如果他们有相同的坐标，开始应该在结束之前。
4. 将 score 初始化为零。
5. 从头到尾迭代排序数组。如果元素开始，增加 score。如果元素结束，则递减 score.
6. 答案将是整个迭代过程中 score 的最大值。

示例：

对于输入<0, 4>, <2, 6>, <4, 6>，有6个事件：

0 begin
4 end
2 begin
6 end
4 begin
6 end

排序是这样安排这些事件的：

0 begin
2 begin
4 begin
4 end
6 end
6 end

然后计算分数：

initial : score = 0
0 begin : score = 1
2 begin : score = 2
4 begin : score = 3
4 end   : score = 2
6 end   : score = 1
6 end   : score = 0

现在你知道答案是3了。