合并重叠的日期范围 - Java

Question

我有一个任务 class 如下所示（使用 Java 8 次 API）。

class Task {
    LocalDateTime start;
    LocalDateTime end;
    Set<String> actionItems;
}

我有两个包含此类任务实例的排序列表（首先按开始，然后按结束），比方说 List<Task> tasksList1 和 List<Task> tasksList2。我想合并重叠的任务（通过在需要时打破任务，并将重叠的其他任务中的 actionItems 添加到一个新的任务对象中）。

例如，假设我有一个名为 T1 的任务，从 01/01/2015 开始到 01/31/2015 结束，其中包含操作项 A 和 B。然后用户创建了一个新任务 T2，它开始2015 年 1 月 15 日至 2015 年 2 月 15 日结束，并将行动项目 C 添加到其中。当我合并时，我应该得到三个任务对象如下。

任务 X - 从 01/01/2015 到 01/15/2015，包含行动项目 A、B
任务 Y - 从 2015 年 1 月 15 日到 2015 年 1 月 31 日，包含项目 A、B 和 C
任务 Z - 从 2015 年 1 月 31 日到 2015 年 2 月 15 日，包含项目 C

想象一下，如果我的两个列表中的任务对象在时间轴中看起来如下所示：

> [-----]      [-----]         [----]         [-----------------]
>     [-----]           [---------------]         [------]

那么生成的任务列表将包含如下任务。

> [--][-][--]  [-----]  [-----][----][--]      [-][------][-----]`

重叠任务应将 actionItems 与在重叠期间重叠的两个任务相结合。

处理此问题的最有效方法是什么？目前我正在尝试使用 PeekableIterator 的不同选项，但还没有成功。也欢迎任何使用 JodaTime 而不是 Java 8 APIs 的解决方案。

Answer 1

首先，如果您只关心日期（不关心时间），最好改用 LocalDate。其次，我假设您有一个任务构造函数。所以我使用了以下 Task 对象：

static class Task {
    LocalDate start;
    LocalDate end;
    Set<String> actionItems;

    public Task(LocalDate start, LocalDate end,
            Collection<String> actionItems) {
        this.start = start;
        this.end = end;
        this.actionItems = new HashSet<>(actionItems);
    }

    @Override
    public String toString() {
        return start + ".." + end + ": "+actionItems;
    }
}

这是更一般任务的解决方案，它只是根据您的规则合并给定集合中的所有任务（输入集合不一定排序）：

public static List<Task> convert(Collection<Task> input) {
    NavigableMap<LocalDate, Set<String>> map = new TreeMap<>();
    map.put(LocalDate.MIN, new HashSet<>());

    for (Task task : input) {
        if (!map.containsKey(task.start)) {
            map.put(task.start, new HashSet<>(map.lowerEntry(task.start).getValue()));
        }
        if (!map.containsKey(task.end)) {
            map.put(task.end, new HashSet<>(map.lowerEntry(task.end).getValue()));
        }
        for (Set<String> set : map.subMap(task.start, task.end).values()) {
            set.addAll(task.actionItems);
        }
    }
    List<Task> result = new ArrayList<>();
    LocalDate prev = null;
    Set<String> prevValues = Collections.emptySet();
    for (Entry<LocalDate, Set<String>> entry : map.entrySet()) {
        if (!prevValues.isEmpty()) {
            result.add(new Task(prev, entry.getKey(), prevValues));
        }
        prev = entry.getKey();
        prevValues = entry.getValue();
    }
    return result;
}

核心是NavigableMap，其中每个键是下一个时间段的开始，值是从给定开始到下一个键期间的动作集合（空值对应没有行动的时期）。添加新任务后，现有条目会相应更新。使用示例：

List<Task> res = convert(Arrays.asList(
  new Task(LocalDate.parse("2015-01-01"), LocalDate.parse("2015-01-31"), 
        Arrays.asList("A", "B")),
  new Task(LocalDate.parse("2014-01-01"), LocalDate.parse("2014-01-31"), 
        Arrays.asList("A", "B")),
  new Task(LocalDate.parse("2015-01-15"), LocalDate.parse("2015-02-15"), 
        Arrays.asList("C"))));
res.stream().forEach(System.out::println);

输出：

2014-01-01..2014-01-31: [A, B]
2015-01-01..2015-01-15: [A, B]
2015-01-15..2015-01-31: [A, B, C]
2015-01-31..2015-02-15: [C]

合并重叠的日期范围 - Java

Combining Overlapping Date Ranges - Java

java

algorithm

time

datetime

jodatime