Find a space of time in a set of dates

Question

I come here with a problem I would like to share, I hope anyone can help me to solve this. I'll try to describe the problem as clear as possible. The problem is as follows.

I have a program in java, with a method that receives a set of dates (java.util.Date).

| start    end  |
| date1    date1|
<--------------->
|       | start        end  |     |                   |
|       | date2        date2|     |                   |
|       <------------------->     |                   |
|                                 | start        end  |
|                                 | date3        date3|
|                                 <------------------->

In the example above, we have three dates, where the first two intersect, but start-date3 is after end-date2. For my business rule, here's an space of time.

Now consider the next scenario.

| start    end  |
| date1    date1|
<--------------->
|       | start        end  |     |                   |
|       | date2        date2|     |                   |
|       <------------------->     |                   |
|                                 | start        end  |
|                                 | date3        date3|
|                                 <------------------->   
|  |                                                      |
|  | start                                           end  |
|  | date4                                           date4|
|  <------------------------------------------------------>

In this case, even when there's an space of time between end-date2 and start-date3, it's considered that it doesn't exist a space of time, because the time between start-date4 and end-date4 covers such space.

I would like to retrieve true, if there's one or more spaces of time, otherwise I will return false.

The only way I've tried is loop every start/end relationship, comparing end-date1 vs start-date2 vs start-date3 and so on ... that's not what I would like to apply.

If there's some other ideas, they are all welcome. If you need more information, I'll add it. Thank you.

Answer 1

There's a really simple algorithm for this problem.

1. Create an array of start values, and a separate array of end values.
2. Sort both arrays (independently).

3. Set InRange to 0. Now scan both arrays in merged order; make sure that if the values are the same, you do all the end values before the start values with the same value. For each value in the scan:

   a. If it is from the array of end values: Decrement InRange. If InRange is now 0, you've found the start of a "space of time".

   b. If it is from the array of start values: If InRange is 0, you've found the end of a "space of time". Regardless, increment InRange.

The above algorithm is designed for half-open intervals where the end-value is actually not included in the interval. In the case of dates, you should pretend that a start date is actually the midnight just before the date, while the end date is actually the midnight just after it (so it is the same as the start date of the next day). That affects the way you scan the merged arrays in order. If in your problem the date ranges are inclusive, you can just add 1 to every end-date.

To be clear, in your second example, the two arrays will be:

1. Start date 1, start date 4, start date 2, start date 3
2. End date 1, end date 2, end date 3, end date 4

And the processing order in step 3 will be:

• Start date 1, start date 4, start date 2, end date 1, start date 3, end date 3, end date 4.

You don't really have to create two separate sorted arrays. You could sort all the endpoints (as endpoints) in a single array, where you mark each data as being a start or an end. (Ideally you would want to make sure that end X comes before start X for the same X. Otherwise, the algorithm will occasionally produce zero-length "space of time" ranges, which you'll have to ignore.)

Answer 2

Okay, this is a really "weird" idea, but see if this "concept" is any better.

Basically, the idea is to merge all the overlapping dates into a few "ranges" as possible, this means, that in your first example, you would end up with two distinct ranges (start date 1 to end date 2 and (start date 3 to end date 3) and in your second you would end up with one (start date 1 to end date 4)

So, if the set only has one distinct range, then you have no gaps, other wise, you do.

import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Date;
import java.util.List;

public class TestDateRanges {

    public static void main(String[] args) {
        try {
            List<Date[]> dates = new ArrayList<>(
                    Arrays.asList(
                            new Date[][]{
                                {makeDate("1.1.2015"), makeDate("5.1.2015")},
                                {makeDate("3.1.2015"), makeDate("10.1.2015")},
                                {makeDate("15.1.2015"), makeDate("20.1.2015")},}
                    )
            );

            Collections.sort(dates, new Comparator<Date[]>() {
                @Override
                public int compare(Date[] o1, Date[] o2) {
                    return o1[0].compareTo(o2[0]);
                }
            });

            List<Date[]> ranges = new ArrayList<>(dates.size());
            Date[] baseRange = null;
            for (Date[] range : dates) {
                if (baseRange == null) {
                    baseRange = range;
                    ranges.add(baseRange);
                } else if ((baseRange[0].before(range[0]) || baseRange[0].equals(range[0])) && (baseRange[1].after(range[0]) || baseRange[1].equals(range[0])) {
                    System.out.println("> Overlap " + format(baseRange) + " <-> " + format(range));
                    if (range[1].after(baseRange[1])) {
                        baseRange[1] = range[1];
                    }
                } else {
                    System.out.println("> Out of range " + format(baseRange) + " >-< " + format(range));
                    baseRange = range;
                    ranges.add(baseRange);
                }
            }

            System.out.println("Has " + ranges.size() + " distinct ranges");

            for (Date[] range : ranges) {
                System.out.println(format(range));
            }
        } catch (ParseException exp) {
            exp.printStackTrace();
        }
    }

    public static final DateFormat FORMAT = new SimpleDateFormat("d.M.yyyy");

    protected static final Date makeDate(String value) throws ParseException {
        return FORMAT.parse(value);
    }

    private static String format(Date[] baseRange) {
        return FORMAT.format(baseRange[0]) + "->" + FORMAT.format(baseRange[1]);
    }

    private static Date[] makeDateRange(String from, String to) throws ParseException {
        return new Date[]{makeDate(from), makeDate(to)};
    }

}

Which outputs...

> Overlap 1.1.2015->5.1.2015 <-> 3.1.2015->10.1.2015
> Out of range 1.1.2015->10.1.2015 >-< 15.1.2015->20.1.2015
Has 2 distinct ranges
1.1.2015->10.1.2015
15.1.2015->20.1.2015

Now, if I change the set to...

List<Date[]> dates = new ArrayList<>(
        Arrays.asList(
                new Date[][]{
                    {makeDate("1.1.2015"), makeDate("5.1.2015")},
                    {makeDate("3.1.2015"), makeDate("10.1.2015")},
                    {makeDate("15.1.2015"), makeDate("20.1.2015")},
                    makeDateRange("2.1.2015", "25.1.2015")
                }
        )
);

it outputs...

> Overlap 1.1.2015->5.1.2015 <-> 2.1.2015->25.1.2015
> Overlap 1.1.2015->25.1.2015 <-> 3.1.2015->10.1.2015
> Overlap 1.1.2015->25.1.2015 <-> 15.1.2015->20.1.2015
Has 1 distinct ranges
1.1.2015->25.1.2015

This is just a conceptual idea and you should beware, that this example will change the data in the dates list, so you will want to be sure that you have a copy of the data first