计算被两条竖线切割的水平线段数量

Question

计算被两条竖线切割的水平线段数量

3

给定N条水平线段，它们有起点和终点（即A和B），没有重叠的限制条件。这意味着我们有从（A,0）到（B,0）的线段。现在我们可以通过这些线段画出两条垂直线。我们需要找到这两条线能够穿过的最大线段数量。（如果一条垂直线触碰到任何一个水平线段，也要计算在内）

例如：假设我们有5条线段：

接下来我们将画两条与Y轴平行的线，分别穿过X轴上的2点和4点。这两条线将触及所有五个线段。因此，答案为5。

但是假设我们有三个线段：

1 2
3 4
5 6

答案是2，因为在这种情况下不可能触碰超过两个点。

如何解决这个问题？请帮忙。

注意：1≤N≤10^5且0≤A＜B≤10^9。

- ho_dare ago

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Answer 1

这个问题有几个提示。

提示1

设置一个变量count为0。

现在对开始和结束事件进行排序，并按照递增顺序循环遍历事件。

如果遇到开始事件，将count增加1。

如果遇到结束事件，将count减少1。

算法的每一步中，count表示当前x位置上重叠的区间数。

提示2

上面的提示展示了如何找到与最多区间重叠的单条线。

然而，我们想要找到两条线。所以我们需要能够找到第二条线，它穿过最多数量的区间 - 不包括与第一条线相交的区间。

你可以使用带有延迟传播的线段树（C++代码here）来实现。这样可以在O(logn)的时间内添加区间/查询最大值。

你可以将这个方法与提示1结合起来，只在遇到结束事件时向线段树中添加区间。

伪代码如下：

For each event in sorted order:
   if event.type==start: count += 1
   if event.type==end: count -= 1 and update segment tree to add 1 to all points in range event.start to event.end
   current_value = count + maximum value in segment tree
   best_value = max(best_value,current_value)

整体复杂度将为O(nlogn)，其中包括初始排序的O(nlogn)和扫描以找到最佳线对的O(nlogn)。