java - 通过开始和结束时间戳搜索和检测对象列表中的重叠

Question

我有一个列表，我想通过设备字符串属性检测列表中重叠的任务。所以，Mission 会是这样的:

public class Mission {
    private String id;
    private String device;
    private long startTime;
    private long endTime;
}

我收到一个列表，并希望在以下情况下返回子任务属性设置为“重叠”的相同列表:

• 同一设备在其范围内(timestampstart 到 timestampend)有另一个任务。

回想一下，我需要标记所有重叠的任务。当我在列表中找到它们时，标记当前(如果匹配)和列表中遇到的。

我想以尽可能低的成本来做这件事。非昂贵的操作。

Answer 1

如果你有可能使用额外的内存，我可以为你提供以下算法

1. 创建 HashMap<String, TreeSet<Mission>> map其中 device是一把 key 。

2. TreeSet 必须按 startTime 排序.示例 new TreeSet<>(Comparator.comparingLong(Mission::getStartTime))

3. 初始化map使用列表中的数据。这里的主要想法是按 device 对数据进行分组并按 startTime 对分组数据进行排序.

4. 然后遍历您的列表并应用以下算法:

   1. 在创建的 map 中找到 TreeSet:TreeSet<Mission> set = map.get(item.device) .如果它的大小等于 1，那么您可以移动到列表中的下一个项目，因为集合中的唯一项目与列表中的原始项目具有相同的 ID。
   2. 从步骤 1 中收到的集合中找到包含元素的子集，其中 startTime低于item.endTime .如果它的大小等于 1，那么您可以移动到列表中的下一个项目，因为子集的唯一项目与列表中的原始项目具有相同的 ID。代码示例:set = set.headSet(new Mission().setStartTime(item.getEndTime()))
   3. 从步骤 2 中找到子集中的第一个元素，即 endTime不止原创item.startTime .我建议您按向后顺序移动子集 set.descendingIterator()如果您找到一个并且它的 ID 不等于原始项目 ID，那么您可以将项目标记为重叠并移至列表的下一个项目。否则对子集的下一个元素重复步骤 3，直到结束。