algorithm - 在不同区间内找到共同点

Question

给定一个“线程”列表，其中包含 2 个变量 - 开始时间和结束时间 - 实现一个函数，该函数将在某个时间 t 返回所有正在运行的线程。优化它。(比 O(n) 更快)

---

我的解决方案是遍历列表——时间复杂度为 O(n)。有谁知道如何在这里实现比 O(n) 更快的速度？

class MyThread{
Thread thread;
long start;
long end;
}//the object in the list

//function to find "threads"
public List<Thread> matchingInterval(List<MyThread> list) {
    List<Thread> found = new ArrayList<Thread>();
    Set<Thread> runningThreads = Thread.getAllStackTraces().keySet();
    long instant = System.currentTimeMillis();
    for(MyThread el: list)
        if(el.start <= instant && el.end >= instant && runningThreads.contains(el.thread))
            found.add(el.thread);
    return found;
}

编辑:

目标是在某个时间 t 返回所有正在运行的线程。我的解决方案假设 time t 是调用我的函数时的时间(加/减误差) ，因此我的 long instant = System.currentTimeMillis(); 调用者是否有可能指定某个任意时间？如果是，那么我发现这个问题实际上与线程本身无关，因此我不需要获取实际的 runningThreads。

还有一点:仅仅因为一个线程是活着的，它就是在运行吗？

Answer 1

如果您的列表已排序，您可以使用任何搜索算法(例如分而治之)实现比 O(n) 更快的速度。对于未排序的列表，无法实现比 O(n) 更快的速度，因为您必须查看每个项目