Q

查找一組間隔的最大深度

2017-10-06 73 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 ]。 –

相關問題