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

Question

我有一个列表，我想通过设备字符串属性检测列表中重叠的任务。所以，使命将是：

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

我收到一个列表并希望返回相同的列表，其中子任务属性设置为“重叠”，如果：

• 在其范围内（从时间戳开始到时间戳结束），同一设备还有另一个任务。

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

我想用尽可能少的成本来做到这一点。非昂贵的操作。

标签： javaalgorithmsortingdata-structurescollections

Answer 1

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

1. 创建HashMap<String, TreeSet<Mission>> map哪里device是关键。

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

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

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

   1. 在创建的地图中找到 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比 original 多item.startTime。我建议您以向后的顺序移动子集set.descendingIterator()如果您找到一个并且它的 id 不等于原始项目 id，那么您可以将项目标记为重叠并移至列表的下一个项目。否则对子集的下一个元素重复步骤 3 直到结束。