Calculating total time when given ranges of time that may overlap

Question

I am working on a CodeEval problem called Working Experience.

I am given input in the form of "Month Year-Month Year" as ranges of time that someone has worked. The goal is to calculate the total time worked, however overlaps do not count, such that if the range Jan 2014-Dec 2014 appeared twice, the total time worked would still only be 12 months (1 year).

Due to the input constraints, The dates are in range [Jan 1990, Dec 2020]. The end date > begin date. I believe I can force myself to an answer, but it doesn't exactly satisfy me for obvious reasons.

Set of input would look like:

Aug 2013-Mar 2014; Apr 2013-Aug 2013; Jun 2014-Aug 2015; Apr 2003-Nov 2004; Apr 2014-Jan 2015

Extremely forced solution: Make a boolean array that represents the months from Jan 1990 to Dec 2020. Easy to handle overlaps, just trigger flag changes if a range contains a specific month. Sum up the number of "trues" or something at the end.

I am trying to implement my solution in Java, it seems that quite a few people have done this problem in Python however I am unfamiliar with it, so I not even too clear on their algorithmic approach in their solution.

I have not worked with Date, Time, Calendars and whatnot much in Java. So I am unsure if any of these would be of any help to me. I think I am having the most issue dealing with overlaps and how to overcome them.

Answer 1

1. Sort the ranges by their starting dates
2. Combine adjacent ranges if they overlap.
3. This will leave you with ranges that do not overlap.

Answer 2

Elaborating on the correct answer by Scott Hunter…

Joda-Time

I woud use Joda-Time because of its classes to define a span of time: Interval, Period, and Duration.

Parse

I would parse the string inputs to get a DateTime object in UTC for the first of each month. For the second (ending) month, I would call plusMonths(1) because Joda-Time uses the Half-Open approach to ranges where the beginning is inclusive while the ending is exclusive. So, for example, if January 2014-February 2014 means two months (a closed range), I would get the first of January and first of March as the pair of DateTime objects to pass to the Interval constructor.

Sort

Collect those Interval objects, sort by start value.

The Interval class does not implement the Comparable interface, so it does not support sorting. You have to add support for sorting as described the correct answer by Jon Skeet in this question, Sort Intervals in Joda-Time.

Consolidate

Then examine each sequential pairing, calling overlap method to see if they, well, overlap. Might want to test with the abuts method as well, but I've not thought that through.

Sadly, Joda-Time lacks a way to combine a pair of Interval objects (as far as I know). So roll-your-own union method as I provided in this answer to another question, Make a union of two Joda-Time Interval objects.

Sum Days

Lastly, add up the length of time of each unified interval.

For date-time values, we could go either of two ways to account for that time. We might want a number of months, days, hours, and such. Or we might want an exact amount of time (milliseconds). The first is handled by the Period class in Joda-Time, the latter by the Duration class. An interval can be converted to either. StackOverflow has examples of both.

But in this Question, we only care about days (I assume, not actually specified). So use the Days class and its daysIn method to calculate the number of days in each interval.

---

Be aware that the java.util.Date and .Calendar and related classes bundled with Java are notoriously troublesome, confusing, and flawed. Avoid them. Instead use either Joda-Time or the java.time package built into Java 8 (inspired by Joda-Time, defined by JSR 310). If you must use the old bundled classes only for your challenge/homework, well… best of luck. There are many examples on StackOverflow to help. Those classes are not intuitive so be sure to study examples before making any attempts.