Intersecting overlapping intervals in Java

Question

I have an input set of date ranges that may overlap. Instead of combining these overlapping date ranges, I want to create new date ranges with adjusted dates, e.g.:

|---------------------–|
        |-----| 
            |--------------–|

should end up in:

|-------|---|-|--------|----|

Is there an efficient way to solve this with Java?

Thanks in advance!

UPDATE: I didn't mention my own approach in my first question, so here it is: I'd simply take the start and the end date of an interval and add it to a sorted set. Afterwards I'd iterate over the set and create new intervals based on re-ordered dates.

Solution 1

To solve such problem, sort your intervals using start date as first criteria and end date as second. This way you can intersect the intervals in a single iteration. If your interval is overlapped by another interval that starts no sooner, then its successor in the sorted order should be an overlapping interval and so on.

Solution 2

The basic idea:

• Split up each interval into start and end points
• Sort the points
• Iterate through the points and create the new intervals between all neighbouring points.
  Keep track of startIntervals - endIntervals and whenever this number is 0, there should be no interval in that range.

Solution 3

You could use Guava's Range support. Haven't used it with Date objects but it could work. Combined with RangeSet you could add all date ranges and then check if a Date is in the ranges, get the complete range, etc.

Solution 4

Using java.time

Let's use the modern java.time classes.

The LocalDate class represents a date-only value without time-of-day and without time zone.

Create a little class DateRange to hold the stop and start dates.

public class DateRange {
    public LocalDate start , stop ;

    public DateRange ( LocalDate start , LocalDate stop ) {
        if(stop.isBefore(start)){
            throw new IllegalArgumentException ("The stop date is before the start date." );
        }
        this.start = start;
        this.stop = stop;
    }

    @Override
    public String toString () {
        return "DateRange{ " + "start=" + start + ", stop=" + stop + " }";
    }

}

Instantiate objects of that class, and collect.

    List<DateRange> ranges = new ArrayList<> ( 3 );
    ranges.add ( new DateRange ( LocalDate.of ( 2017 , Month.JANUARY , 17 ) , LocalDate.of ( 2017 , Month.MARCH , 7 ) ) );
    ranges.add ( new DateRange ( LocalDate.of ( 2017 , Month.FEBRUARY , 12 ) , LocalDate.of ( 2017 , Month.FEBRUARY , 16 ) ) );
    ranges.add ( new DateRange ( LocalDate.of ( 2017 , Month.FEBRUARY , 14 ) , LocalDate.of ( 2017 , Month.MARCH , 25 ) ) );

    System.out.println ( "ranges: " + ranges );

Extract each start and each stop, collecting into a List.

    // Intersect and combine to create a sequence of new DateRange objects.
    // Collect each start & stop as individual `LocalDate` objects.
    List<LocalDate> dates = new ArrayList<> ( ranges.size () * 2 );
    for ( DateRange range : ranges ) {
        dates.add ( range.start );
        dates.add ( range.stop );
    }

Sort the dates. As shown in the Question, the various ranges may overlap with one another. We need them in chronological order so as to make new abutting date ranges.

    // Sort the collection of dates.
    Collections.sort ( dates );

Loop the sorted dates, using each as a start date and the following date as the stop.

    // Loop the sorted dates, creating DateRange objects as we go.
    List<DateRange> rangesOutput = new ArrayList<> ( dates.size () ); // Not an exact initial capacity but good enough.
    for ( int i = 1 ; i < dates.size () ; i ++ ) {
        LocalDate start = dates.get ( i - 1 ); // Subtract one for silly index counting.
        LocalDate stop = dates.get ( i + 1 - 1 ); // Subtract one for silly index counting. Or use ( i ) instead.
        if (  ! start.equals ( stop ) ) {  // If not equal, proceed. (If equal, ignore and move on to next loop.)
            DateRange range = new DateRange ( start , stop );
            rangesOutput.add ( range );
        }
    }
    System.out.println ( "rangesOutput: " + rangesOutput );

When run.

ranges: [DateRange{ start=2017-01-17, stop=2017-03-07 }, DateRange{ start=2017-02-12, stop=2017-02-16 }, DateRange{ start=2017-02-14, stop=2017-03-25 }]

rangesOutput: [DateRange{ start=2017-01-17, stop=2017-02-12 }, DateRange{ start=2017-02-12, stop=2017-02-14 }, DateRange{ start=2017-02-14, stop=2017-02-16 }, DateRange{ start=2017-02-16, stop=2017-03-07 }, DateRange{ start=2017-03-07, stop=2017-03-25 }]

See this code live at IdeOne.com.

---

About java.time

The java.time framework is built into Java 8 and later. These classes supplant the troublesome old legacy date-time classes such as java.util.Date, Calendar, & SimpleDateFormat.

The Joda-Time project, now in maintenance mode, advises migration to the java.time classes.

To learn more, see the Oracle Tutorial. And search Stack Overflow for many examples and explanations. Specification is JSR 310.

Where to obtain the java.time classes?

• Java SE 8 and SE 9 and later
  • Built-in.
  • Part of the standard Java API with a bundled implementation.
  • Java 9 adds some minor features and fixes.
• Java SE 6 and SE 7
  • Much of the java.time functionality is back-ported to Java 6 & 7 in ThreeTen-Backport.
• Android
  • The ThreeTenABP project adapts ThreeTen-Backport (mentioned above) for Android specifically.
  • See How to use ThreeTenABP….

The ThreeTen-Extra project extends java.time with additional classes. This project is a proving ground for possible future additions to java.time. You may find some useful classes here such as Interval, YearWeek, YearQuarter, and more.

Solution 5

Using my time library Time4J, following convenient solution is possible without much brainstorming about the real implementation:

// create the intervals
SimpleInterval<Date> i1 = SimpleInterval.between(new Date(0L), new Date(5000L));
SimpleInterval<Date> i2 = SimpleInterval.between(new Date(0L), new Date(7000L));
SimpleInterval<Date> i3 = SimpleInterval.between(new Date(1000L), new Date(2000L));

// collect the intervals
IntervalCollection<Date> icoll =
    IntervalCollection.onTraditionalTimeLine().plus(i3).plus(i2).plus(i1);

// split and iterate
for (ChronoInterval<Date> interval : icoll.withSplits().getIntervals()) {
    System.out.println(interval);
}

Output:

[Thu Jan 01 01:00:00 CET 1970/Thu Jan 01 01:00:01 CET 1970)
[Thu Jan 01 01:00:01 CET 1970/Thu Jan 01 01:00:02 CET 1970)
[Thu Jan 01 01:00:02 CET 1970/Thu Jan 01 01:00:05 CET 1970)
[Thu Jan 01 01:00:05 CET 1970/Thu Jan 01 01:00:07 CET 1970)

The main adjustment after defining and gathering all the intervals is just calling withSplits() on the interval collection.

Another advantage is the option to slightly adjust the code such that working with other types like the class java.time.Instant from Java-8 or the built-in Time4J-types like Moment, PlainDate, PlainTimestamp etc. is easily possible, too.

View more solutions

Comments

[Joni]

It looks like all you want to do is take the start and end dates and sort them. Does that solve your problem?

[Bernhard Barker]

I imagine dealing with overlap with this algorithm could end up being rather complicated.

[Ivaylo Strandjev]

Actually not really. You only check the end of the current interval against the beginning of the next interval in the ordering. I have written this algorithm many times and it is not hard at all IMHO.

[Bernhard Barker]

In the example in the question, you need to keep track of the end of the first interval after partially processing both the second and third. It's not too complicated, but I believe it would require an additional data structure for the end points. Splitting up the intervals into start and end points from the start would be simpler.