Find time in date set

Question

I am coming here with a problem that I would like to share, I hope someone can help me solve this problem. I will try to describe the problem as clearly as possible. The problem is as follows.

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

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

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

Now consider the following scenario.

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

In this case, even when there is time between the end-date2 and start-date3, he believed that there is no time, since the time between the start date4 and the end date4 covers such a space.

I would like to get true if there is one or more time intervals, otherwise I will return false.

The only way I tried is the cycle of each start / end relationship, comparing end date1 with starting number2 and starting number3, etc .... this is not what I would like to apply.

If there are any other ideas, they are all welcome. If you need more information, I will add it. Thanks.

Answer 1

Well, this is really a "strange" idea, but look if this "concept" is better.

Basically, the idea is to combine all overlapping dates into several “ranges” as much as possible, which means that in your first example you will get two different ranges (start date 1 to end date 2 and (start date 3 to end date 3), and in the second you get one (start date 1 to end date 4)

So, if a set has only one separate range, then you have no spaces, others are reasonable, 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("dMyyyy"); 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)}; } } 

What exits ...

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

displays ...

 > 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 changes the data in the dates list, so you want to make sure that you have the first copy of the data

Answer 2

There really is a simple algorithm for this problem.

• Create an array of starting values ​​and a separate array of ending values.
• Sort both arrays (independently).

• Set InRange to 0. Now scan both arrays in a unified order; make sure that if the values ​​match, you do all the final values ​​before the starting values ​​with the same value. For each value in the scan:

  but. If it is from an array of final values: Decrement InRange. If InRange is now 0, you have found the beginning of the “time space”.

  b. If it is from an array of initial values: if InRange is 0, you have found the end of the “time space”. Regardless, increase InRange.

The above algorithm is intended for half-open intervals, where the final value is actually not included in the interval. In the case of dates, you must pretend that the start date is midnight immediately before the date, and the end date is actually midnight immediately after it (same as the start date of the next day). This affects the way in which the combined arrays are scanned in order. If date ranges are included in your problem, you can simply add 1 to each end date.

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

• Start date 1, start date 4, start date 2, start date 3
• 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 do not need to create two separate sorted arrays. You can sort all endpoints (as endpoints) in one array, where you mark each data as a start or end. (Ideally, you would like to make sure that the end of X is before running X for the same X. Otherwise, the algorithm will sometimes create zero-length "space-time" ranges that you will have to ignore.)