我有一个算法问题，我想看看它是否可以比 O(n) 更好地解决：
我给出了一个包含 n 个元素的表 T，其中每个元素都是一个元组 (s_i, e_i)，其中 s_i、e_i 在 N 中且 s_i < e_i，即每个元组都是某种区间。我必须找到与给定间隔 [t0, t1] 重叠的所有间隔，其中 t0, t1 在 N 和 t0 < t1。此外，我有两个可用的排序列表 S 和 E，分别包含 s 值或 e 值，以及指向 T 中相应条目的索引 i。这些列表分别按 s 值或 e 值排序。（假设 s 和 e 值都是唯一的。）
问题：
我们必须在 T 中找到每个区间/元组 (s_i, e_i)，其中 s_i <= t1 且 e_i >= t0。
到目前为止我的想法：
我们可以通过应用一个区间边界来排除一些元素，即在 S 中搜索 t1 或在 E 中搜索 t0。这为我们提供了剩余元素的列表 L：
L <- {e in E | e >= t0} or L <- {s in S | s <= t1}
但是，无论我们执行哪种搜索，L 中的元素数量都没有下限。此外，如果 s <= t1 或 e >= t0，我们必须分别检查 L 中的每个元素，具体取决于我们之前执行的搜索。
该解决方案的复杂度为 O(n)。
但是，假设 k 是与区间 [t0, t1] 重叠的最大元素数。如果我们假设 k << n，那么复杂度是 O(n/2)，因为我们可以通过选择适当的 L 搜索来排除至少 n/2 个元素。仍然 O(n/2) 在 O(n) 中。
你能想出更好的方法来解决这个问题吗？
（请随时改进这个问题。也许不是很清楚。谢谢）