algorithm - Combining Overlapping Date Ranges - Java

Question

I have a Task class which looks like the following (using Java 8 Time API).

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

I have two sorted (first by start, then by end) lists containing such Task instances, lets say List<Task> tasksList1 and List<Task> tasksList2. I want to combine overlapping tasks (by breaking the tasks if needed, and adding actionItems from other tasks which are overlapping into a single new task object).

For example, assume I have a task called T1 that starts on 01/01/2015 and ends on 01/31/2015, which contains action items A and B. Then a user creates a new Task T2 that starts on 01/15/2015 and ends on 02/15/2015 and adds action item C into it. When I combine, I should get three Task objects as follows.

• Task X - from 01/01/2015 to 01/15/2015, contains action items A, B
• Task Y - from 01/15/2015 to 01/31/2015, contains items A,B and C
• Task Z - from 01/31/2015 to 02/15/2015, contains item C

To visualize, if my task object from the two lists look like the following in a timeline:

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

Then the resulting task list would contain tasks as follows.

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

Overlapping tasks should have the actionItems combined from both of the tasks that overlap for the period in which they overlap.

What is the most efficient way to handle this? At the moment I'm trying out different options with a PeekableIterator, but no luck yet. Any solutions using JodaTime instead of Java 8 APIs is also welcome.

Answer 1

First if you care about dates only (don't care about times), it's better to use LocalDate instead. Second, I assume that you have a task constructor. So I used the following Task object:

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;
    }
}

Here's the solution of more general task which just merges all the tasks in given collection according to your rules (the input collection is not necessarily sorted):

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;
}

The core thing is the NavigableMap where each key is the start of the next time period and the value is the collection of actions for the period from given start until the next key (empty values correspond to the periods without actions). Upon adding the new task existing entries are updated accordingly. Usage example:

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);

Output:

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]