找到一组间隔的最大深度

Question

给定一组区间 I，每个元素的形式为 [a_i, b_i]，在 O(n*logn) 时间内找到最大深度的终点 b_i。将 x 的深度定义为点“刺穿”（或相交）的间隔数。如果两个端点深度相同，则返回较小的一个。

---

尝试：

我不知道如何在 O(n * logn) 时间内找到它。我理解用于查找一组间隔的刺伤集的贪心算法，但是以严格的 O(n * log n) 时间查找终点似乎非常不同。

我可以尝试首先对间隔进行排序，然后强力得出最大深度终点，但这并不能保证 O(n * log n) 时间。

Answer 1

您可以尝试以下方法：

• 对点 a_i 和 b_i 进行排序（一起在一个数组中）
• 遍历排序数组，当遇到“a”点（间隔开始）时增加计数器（深度），遇到“b”点（间隔结束）时减少计数器（深度） - 在这里您可以找到最大的“b”点深度

Answer 2

在 C++ 中，您可以维护向量数据，同时将间隔作为输入。只需将起点推入 make_pair(start_point,0)，0 表示起点，同样，1 表示间隔结束。 现在执行以下操作：-

根据第一个索引对整个向量进行升序排序
现在从头开始遍历向量并初始化变量 iter=0, vector
2. > a={make_pair(0,-inf)} -> 来存储 max_depth 和对应的端点。
如果第二个索引为0，则执行iter++；否则如果是1，则迭代--。
当你执行 iter++ 时，检查 if(a[0].first
4. 在执行 iter-- 时，检查 if(iter == a[0].first) 然后 if(a[0].second
5. < data[0].first) then a[0].second=data[i].first;
以这种方式遍历整个向量后，a[0].first是最大深度，a[0].second是maximum_depth对应的终点。