間隔の集合の最大深さを求める

Question

[I_i、b_i]という形式の各要素がある場合、最大深度の終点b_iをO（n * logn）時間で見つける。ポイントの深さを「刺す」（または交差する）間隔の数としてxの深さを定義します。 2つの終点の深さが同じ場合は、小さい方を返します。

---

試み：

私はO（N * LOGN）の時間でそれを見つけるためにどのようには考えています。私は間隔のセットの刺すセットを見つけるための貪欲なアルゴリズムを理解していますが、厳密にO（n * log n）時間を持つ終点を見つけることは非常に異なっているようです。

私は最初に区間を並べ替えることができますが、最大深さの終点をブルートフォースで実行できますが、これはO（n * log n）時間を保証しません。

Answer 1

あなたは次のことを試すことができます：あなたは「」ポイントを（遭遇したときにソートされた配列は、カウンター（深さ）を大きくトラバース（一緒に1列で）あなたのポイントa_iをし、b_i

• ソート
• 最大の深さで "b"点を見つけることができます。