java - 删除数组列表中的相交值

Question

我有这样一个类

    public class Func {
    String id;
    long startTime;
    long endTime;
}

在其中一种方法中我有这些类对象的列表

List<Func> funList = new ArrayList<Func>();

从这个 funList 中删除其 startTime 和 endTime 与同一列表中的另一个对象相交的对象的最佳方法是什么。

我能想到的一种方法是获取列表中的每个对象并与其他对象进行比较，如果相交则将 id 放入其他数据结构中。在将每个对象与其他对象进行比较后，遍历保存 ID 的数据结构并将它们从列表中删除。

Answer 1

1. 按开始时间降序、结束时间升序排序。
2. 从左到右扫描数组，持有当前最大右端的元素/
   1. 如果新项的左端小于当前最大右端，则将两者都标记为删除。
   2. 如果需要，更新最大权限。

复杂度:O(n ln n)

编辑示例:

1. (1, 3) (2, 4) (5, 6)
2. curmax = -inf
3. curmax = 3
4. 2 < 3 - 将第一个和第二个标记为“差”。 curmax = 4
5. 5 > 4 - 什么都不做。 curmax = 6。
6. (5,6) - 是唯一好的片段。