1

I have an array of dates range, each date range has it’s own start date, end date and unique Id. I want to have all of the overlapping date ranges (knowing which range overlap with whom and on what range, e.g. it could even be 3 dates range [1,3,8] that overlapped between 08:00-08:10 and the [1.3] overlapped between 08:00-18:15)

I found my question over here : Datetime -Determine whether multiple(n) datetime ranges overlap each other in R But the answer was in R and I didn’t manage to follow the logic

I do know the solution of tuning minute by minute between the first start date and the last end date and check which dates range contain the minutes but I’m hoping to get more elegant solution that won’t get slow with large amount of data

I will be happy to receive answers in C#, JavaScript, typescript, python, java or just English explanation of the logic (I prefers without third part libraries except maybe moment js)

הדר דיין
  • 31
  • 4
  • 1
    To get people on SO helping, you need to make your question as easy as possible for people to help. SO has the insert snippet option. If you create a simple snippet with some example data, and expected results you will most likely get more help. – Keith Feb 26 '18 at 14:32
  • What's the expected output for `[(8:00, 9:00), (8:30, 11:00), (10:00, 11:30)]` ? – גלעד ברקן Feb 26 '18 at 14:44

2 Answers2

1

Half-Open

Generally the best practice in date-time handling is to define a span of time using the Half-Open approach where the beginning is inclusive while the ending is exclusive.

So a day starts with the first moment of one day and runs up to, but does not include, the first moment of the following day. This avoids the problem of trying to determine the infinitely-divisible fractional second of the last moment of the first day.

A month span starts with the first of the month and runs up to, but does include, the first day of the following month. So the month of February runs Feb 1st to March 1st, with no need to determine Leap Year, and no need to determine the length of any month.

Lunch period starts with noon and runs up to, but does not include, 1 PM: 12:00 – 13:00. The next class period runs from 1 PM to 2 PM: 13:00 – 14:00. This lunch period and class period nearly abut one another but do not overlap (because the lunch 13:00 is exclusive).

Also, using the Half-Open approach consistently throughout your codebase makes your code easier to read, with less cognitive burden. And the Half-Open approach makes intervals of stop-start moments abut one another nicely for easier comparisons.

Comparison

Comparing intervals is easy.

For overlap, ask if the start of interval X is before the stop of interval Y AND if the the stop of interval X is after the start of interval Y.

( X.start > Y.stop ) && ( X.stop > Y.start )

Objects

On Object-Oriented environments you should be writing a class to represent each stop-start interval. Build on the comparison code with methods such as “contains”, “overlaps”, etc.

java.time

In Java, we are fortunate to have the best date-time framework in the industry, java.time.

The built-in functionality is further extended by the classes of the ThreeTen-Extra project (the definition of java.time having been JSR 310).

In ThreeTen-Extra you’ll find the Interval class for a pair of Instant objects. An Instant is a moment, a point on the timeline in UTC, with a resolution of nanoseconds. For a pair of date-only values (LocalDate), use the LocalDateRange class.

Both classes have already implemented all the comparison methods you’ll likely need.

  • abuts
  • contains
  • encloses
  • equals
  • intersection
  • isAfter
  • isBefore
  • isConnected
  • isEmpty
  • overlaps
  • span
  • union

These classes are open-source so you may peruse the algorithms.

Note that intersection gives you an interval of the overlap between a pair of intervals.

The union method gives you an interval with the earliest start and the latest stop. You can maintain an ever-growing unioned-interval of all the comparisons made so far. That tells you if the next comparison lies entirely before or entirely after all the previously-compared intervals, and thus saves you from needless comparisons.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
  • 1
    Calculating all of the pairwise intersections between intervals is `O(n^2)`. Assuming that you don't have very large intersections, this problem can be solved in `O(n log(n))` without any fancy classes. – btilly Feb 26 '18 at 17:27
  • Java != JavaScript (so your post does not make any sense here as answer) – Meno Hochschild Feb 26 '18 at 18:37
1

The standard logic for this problem is to turn your intervals into pairs of events, the point at which it opens, and the point where it closes. Then sort the events by date, then open/closed. (If you sort closed in front of open, you DO NOT count as an intersection when one ends right when another opens. If you sort open in front of closed, you do count those as intersections.) And now walk through the sorted list, keeping track of which intervals are currently open and you can read off your answer.

btilly
  • 43,296
  • 3
  • 59
  • 88