Q

查找一组间隔的最大深度

2017-10-06 102 views 0 likes

0

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

尝试：

我不知道如何找到它的O（N * LOGN）的时间。我理解寻找一组间隔的插入集合的贪婪算法，但严格地用O（n * log n）时间找到一个终点似乎是非常不同的。

我可以尝试先排序间隔，然后蛮力强制最大深度终点，但这并不能保证O（n * log n）时间。

2017-10-06 thestateofmay

A

回答

2

你可以尝试以下方法：

排序您点A_I和b_i（放在一个阵列）
遍历数组排序增加一个计数器（深度），当你遇到一个“A”点（开始间隔），并减少“b”点（间隔结束） - 在这里你可以找到你的最大深度的“b”点

2017-10-06 22:39:03 algrid

+0

正确，但你必须小心排序“a “在”b“之前，如果它们具有相同的值。例如：[0，1]，[1,2] - 最大深度为2，这意味着您必须将数字排序为[a0，a1，b1，b2]而不是[a0，b1，a1，b2 ]。 –

相关问题