-1

令 T 为给定的区间树（大小为 n），i 为区间。令 k 为 T 中与 i 重叠的区间数。我需要找到一种算法来在时间 O(min(n, k log n)) 中列出所有这些。

4

1 回答 1

0

通常，您只需要遍历树并在有k重叠间隔时停止。
让我们用 标记您当前正在检查的范围，t然后您需要按如下方式进行检查。 第一个间隔是，第二个是你的.ti
ti

|------|
  |--|

添加t，您可以停止迭代。 

  |--|
|------|

添加t并左右移动。

    |------|
  |---|

添加t并仅向左移动

|------|
     |---|

添加t并正确运行

      |------|
|---|

向左走（不添加t）

|------|
         |---|

向右走（不添加t）

于 2018-03-14T08:34:12.327 回答