Split overlapping and add missing intervals

Question

I have a set of [startdate,enddate] intervals which can be overlapping and contain gaps. My goal is to have a continuous new list of intervals, without gaps and without any overlapping dates.

Example of ranges:

[-----------------------------------A-----------------------]
[-B]
   [-C]
      [D]
                  [-----E-----]
                              [-----F----]
                                                                    [-----G-----]                

A [2009-01-01 - 2014-01-01]     ~5 years
B [2009-01-01 - 2009-01-02]     2 days
C [2009-01-02 - 2009-01-03]     2 days
D [2009-01-04 - 2009-01-04]     1 day
E [2010-01-01 - 2011-01-01]     ~1 year
F [2011-01-01 - 2012-01-01]     ~1 year, a gap after this interval
G [2015-01-01 - 2016-01-01]     ~1 year

What I expect is this new list of intervals:

[2009-01-01 - 2009-01-01]
[2009-01-02 - 2009-01-02]
[2009-01-03 - 2009-01-03]
[2009-01-04 - 2009-01-04]
[2009-01-05 - 2009-12-31]
[2010-01-01 - 2010-12-31]
[2011-01-01 - 2012-01-01]
[2012-01-02 - 2014-01-01]
[2014-01-02 - 2014-12-31]
[2015-01-01 - 2016-01-01]

So, for gaps there are new intervals added. Intervals with the same startdate and enddate are perfectly valid and should be handled as such.

I am quite stuck on both the best way to achieve this, even before getting this in an efficient way :(

Any ideas on how to perform this in Java?

Answer 1

You might try the range-package of my library Time4J and use this code:

DateInterval a = DateInterval.between(PlainDate.of(2009, 1, 1), PlainDate.of(2014, 1, 1));
DateInterval b = DateInterval.between(PlainDate.of(2009, 1, 1), PlainDate.of(2009, 1, 2));
DateInterval c = DateInterval.between(PlainDate.of(2009, 1, 2), PlainDate.of(2009, 1, 3));
DateInterval d = DateInterval.between(PlainDate.of(2009, 1, 4), PlainDate.of(2009, 1, 4));
DateInterval e = DateInterval.between(PlainDate.of(2010, 1, 1), PlainDate.of(2011, 1, 1));
DateInterval f = DateInterval.between(PlainDate.of(2011, 1, 1), PlainDate.of(2012, 1, 1));
DateInterval g = DateInterval.between(PlainDate.of(2015, 1, 1), PlainDate.of(2016, 1, 1));

List<DateInterval> intervals = Arrays.asList(a, b, c, d, e, f, g);

IntervalCollection<PlainDate> icoll = IntervalCollection.onDateAxis().plus(intervals);

for (ChronoInterval<PlainDate> gap : icoll.withGaps().getIntervals()) {
    icoll = icoll.plus(gap);
}

System.out.println(icoll.withSplits());

[2009-01-01/2009-01-01],
[2009-01-02/2009-01-02],
[2009-01-03/2009-01-03],
[2009-01-04/2009-01-04],
[2009-01-05/2009-12-31],
[2010-01-01/2010-12-31],
[2011-01-01/2011-01-01],
[2011-01-02/2012-01-01],
[2012-01-02/2014-01-01],
[2014-01-02/2014-12-31],
[2015-01-01/2016-01-01]

Remark about your expected results:

Your statement

My goal is to have a continuous new list of intervals, without gaps and without any overlapping dates.

is realized with the code above. The gaps are added as normal intervals to the whole interval collection before splitting. All date intervals in Time4J are handled as closed intervals by default (configurable). That means for example that an interval like "[2009-01-01/2009-01-01]" consists of only one day (as you also have shown in the first entry of your expected interval list).

However, you didn't seem to expect the interval "[2011-01-01/2011-01-01]", but just this date (interval consisting of only one day) is an overlapping region between intervals E + F and should also appear in your expected interval list.

About interoperability with Java-8:

You can also apply direct conversion methods like toTemporalAccessor() or from(LocalDate) between the types net.time4j.PlainDate and java.time.LocalDate.