algorithm - Combining Overlapping Date Ranges - Java -

i have task class looks following (using java 8 time api).

class task {     localdatetime start;     localdatetime end;     set<string> actionitems; } 

i have 2 sorted (first start, end) lists containing such task instances, lets list<task> taskslist1 , list<task> taskslist2. want combine overlapping tasks (by breaking tasks if needed, , adding actionitems other tasks overlapping single new task object).

for example, assume have task called t1 starts on 01/01/2015 , ends on 01/31/2015, contains action items , b. user creates new task t2 starts on 01/15/2015 , ends on 02/15/2015 , adds action item c it. when combine, should 3 task objects follows.

• task x - 01/01/2015 01/15/2015, contains action items a, b
• task y - 01/15/2015 01/31/2015, contains items a,b , c
• task z - 01/31/2015 02/15/2015, contains item c

to visualize, if task object 2 lists following in timeline:

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

then resulting task list contain tasks follows.

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

overlapping tasks should have actionitems combined both of tasks overlap period in overlap.

what efficient way handle this? @ moment i'm trying out different options peekableiterator, no luck yet. solutions using jodatime instead of java 8 apis welcome.

first if care dates (don't care times), it's better use localdate instead. second, assume have task constructor. used 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 solution of more general task merges tasks in given collection according rules (the input collection not sorted):

public static list<task> convert(collection<task> input) {     navigablemap<localdate, set<string>> map = new treemap<>();     map.put(localdate.min, new hashset<>());      (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()));         }         (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();     (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 navigablemap each key start of next time period , value collection of actions period given start until next key (empty values correspond periods without actions). upon adding new task existing entries 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]