4

Sam is working as a part time truck driver. He gets special allowance if he is driving from 0200 hrs - 0600hrs. His boss wants to know which all trips touched this time period. Below are the details for his last 4 trips.

Trip 1:

StartDateTime : 01-JAN-2017 00.15.00
EndDateTime : 03-JAN-2017 01.45.00

Touched: True

Trip 2:

StartDateTime : 04-JAN-2017 13.00.00
EndDateTime : 05-JAN-2017 13.00.00

Touched: True

Trip 3:

StartDateTime : 06-JAN-2017 00.00.00
EndDateTime : 06-JAN-2017 05.00.00

Touched: True

Trip 4:

StartDateTime : 06-JAN-2017 06.01.00
EndDateTime : 06-JAN-2017 23.00.00

Touched: False

I came up with my own implementation for finding this in java which have few if cases, but i have this feeling somewhere that i am reinventing the wheel. What is the best possible way to find if a date range touches a time range?

Edit: Adding the followed approach

    public boolean isTripTouchingTimeRange(Date startDate, Date endDate, AllowanceDefinition def) {

    int checkConstant = HOURS_IN_A_DAY - (def.getEndMinute() - def.getStartMinute());
    // HOURS_IN_A_DAY = 1440 MINUTES (2400 HRS) ; def.getEndMinute() = 360
    // MINUTES (0600 HRS) ; def.getStartMinute() = 120 MINUTES (0200 HRS)

    DateTime start = new DateTime(startDate);
    DateTime end = new DateTime(endDate);
    if (DateUtil.subtractDates(start.toDate(), end.toDate()) > checkConstant) {
        return true;
    } else if (end.withTimeAtStartOfDay().isAfter(start.withTimeAtStartOfDay())
            && (end.getMinuteOfDay() > def.getStartMinute())) {
        return true;
    } else if (start.getMinuteOfDay() <= def.getEndMinute() && def.getStartMinute() <= end.getMinuteOfDay()) {
        return true;
    }
    return false;
    }
1
  • The Half-Open approach is often wisely used in date-time work for defining spans of time. In Half-Open, the beginning is inclusive while the ending is exclusive. This means your special time span starts at 2 AM and runs up to, but does not include, 6 AM. So your last example would also return false if the 06.01.00 were 06.00.00. Feb 4, 2017 at 16:38

3 Answers 3

2

This problem is similar to intersection of circular values.

If your solution uses a lot of cases, consider trigonometric analogy here. Using of cosine function solves problems with day by day wrapping and nontrivial interval overlaps.

Date and times could be transformed into angles like

TimeAngle = Pi * TimeHrs / 12

Note that both time range and trip times should be "normalized":

  • If trip lasts more than day, it should be replaced by 0..2*Pi angle interval.
    In other cases:
    • define 00:00 of the starting day of trip as 0
    • get starting angle TripStartAngle = Pi * StartTripTimeHrs / 12.
      For example, for 06:00 time angle is Pi*6/12 = Pi/2 = 90 degree (imagine hour hand angle on 24-hrs clock face)
    • get ending angle TripEndAngle = Pi * EndTripTimeHrs / 12. If ending angle is less than starting (due to date change), add 2*Pi.
      For example, for 15:00 time angle is Pi*15/12 = 1.25 * Pi.
      But for 03:00 time angle is
      Pi*3/12 = Pi/4 - less than starting Pi/2, so add 2*Pi, and result is 2.25*Pi
4
  • I am not sure if I understand your answer completely. I don't think this is a complete or the best solution especially when I try to relate to it with the Trip 1 in my question. How will we account for multiple touches? And can you give details/suggest readables for the TimeAngle concept, so that i won't feel naked while commenting on your answer. :)
    – RBz
    Feb 5, 2017 at 15:08
  • As far as I understand, you need to determine fact of time interval intersection, not its number. In this case algorithm is suitable. Using this algorithm, one at first have to "normalize" intervals - if time span is more than day, it is possible to replace it with full-circle angle 0..2*Pi. I'll give some examples for time to angle transformations.
    – MBo
    Feb 5, 2017 at 15:24
  • Added the approach followed by me. From what i understand your approach took my linear consideration of time into a circular fashion.Am I right? I think both works the same way.
    – RBz
    Feb 6, 2017 at 13:10
  • Seems this condition (end.getMinuteOfDay() > def.getStartMinute()) is not enough to return true. Interval intersection requires two if's
    – MBo
    Feb 6, 2017 at 13:34
0

The question is not complete.

Anomalies

In date-time work, we encounter anomalies. Daylight Saving Time (DST) in the most common. But we also have problem of politicians frequently redefining time zones, as has happened in the last few years in Turkey (2016), Russia (2016, 2014, 2011), Venezuela (2016, 2007), and other places.

So you must decide how to handle such anomalies. For example, on DST cutover the day can be 23 or 25 hours long. In the United States, DST means either no 2 AM hour or a 2 AM hour that happens twice. Be aware that DST cutovers happen at other times-of-day in other places outside the US.

Time zone

Unless you choose to ignore such anomalies, you cannot work simply with the date and time-of-day. You need the context of a time zone to make meaning of a date+time.

A date and time-of-day only in date-time work are often called a "local date-time" meaning any locality rather than a specific locality. As such, this does not represent a moment, a point on the timeline. A local date-time a vague idea about a range of possible moments stretching over 26 hours with time zones running as much as 14 hours ahead of UTC and 12 hours behind. Apply a time zone to determine an actual moment, a specific point on the timeline.

2
  • All are points to be noted. But, if we consider finding if a date range touches a time range as a math problem,I think, there is nothing here answering the question.
    – RBz
    Feb 5, 2017 at 12:44
  • The point of my Answer is that it is naïve of you to treat the subject as a simple generic math problem. Date-time work is complicated. Feb 5, 2017 at 16:11
0

I should have written this out in code first, as I think this might've been more straightforward (or at least familiar to me) to think about in millisecond timestamps. I still may go back and do so if I have time.

On a related note, I found Interval trees an interesting read although I didn't pursue it.

I am not convinced the following is correct, especially my 'rule' about how to choose the date component of 0200/0600. Needs moar tests, but. . .

If Sam drives 20 or more hours for a trip then he has touched the time range in some fashion. (ex. Trips 1 & 2)

If Sam drives less than 20 hours for a trip then we can limit our range of possibilities using the duration of his trip.

The date component of 0200/0600 is established according to the start date. If the time component of startDateTime is between 0000 and 0600 (inclusive) then 0200/0600 shares the date component of startDateTime, otherwise it is the following day.

duration = endDateTime - startDateTime mustStartTime = 0200 - duration mustEndTime = 0600 + duration touched = (startDateTime >= mustStartTime && endDateTime <= mustEndTime)

Trip 3

  • StartDateTime: 06-JAN-2017 00.00.00
  • EndDateTime: 06-JAN-2017 05.00.00
  • Touched: True

duration = 5 hours mustStartTime = 2100 = 0200 - 5 mustEndTime = 1100 = 0600 + 5 touched = (0000 >= 2100 && 0500 <= 1100) = (true && true)

Trip 4

  • StartDateTime : 06-JAN-2017 06.01.00
  • EndDateTime : 06-JAN-2017 23.00.00
  • Touched: False

duration = 16hr 59min mustStartTime = 1001 = 0200 - 16 hr 59 min mustEndTime = 2159 = 0500 + 16 hr 59 min touched = false = (0601 >= 1001 && 2300 <= 2159) = (false && false)

Trip 5

  • StartDateTime : 06-JAN-2017 03.00.00
  • EndDateTime : 06-JAN-2017 04.00.00
  • Touched: True

duration = 1 hour mustStartTime = 0100 = 0200 - 1 hour mustEndTime = 0700 = 0600 + 1 hour touched = true = (0300 >= 0100 && 0400 <= 0700) = (true && true)

Trip 6

  • StartDateTime : 06-JAN-2017 00.00.00
  • EndDateTime : 06-JAN-2017 01.30.00
  • Touched: False

duration = 1hr 30 min mustStartTime = 0030 = 0200 - 1hr 30 min mustEndTime = 0730 = 0600 + 1hr 30 min touched = false = (0000 >= 0030 && 0130 <= 0730) = (false && true)

Trip 7

  • StartDateTime : 06-JAN-2017 05.00.00
  • EndDateTime : 06-JAN-2017 06.00.00
  • Touched: True

duration = 1 hour mustStartTime = 0100 = 0200 - 1 hour mustEndTime = 0700 = 0600 + 1 hour touched = (0500 >= 0100 && 0600 <= 0700) = (true && true)

Update

Now with code & test. All assertions are proper! Definitely feels like wheel reinventing!

public class OverlappingDateRangeUtil {

    /**
     * 1000 ms * 60 s * 60 m
     */
    public static final long MS_IN_AN_HOUR = 1000 * 60 * 60;

    public static final long MS_IN_TWO_HOURS = 2 * MS_IN_AN_HOUR;

    public static final long MS_IN_SIX_HOURS = 3 * MS_IN_TWO_HOURS;

    public static final long MS_IN_TWENTY_HOURS = 20 * MS_IN_AN_HOUR;

    private static boolean tripLongerThanTwentyHours(long duration) {
        return duration >= MS_IN_TWENTY_HOURS;
    }

    private static long getTruncDateFor0200And0600(Date start) {
        Calendar cal = new GregorianCalendar();
        cal.setTime(start);

        int startHour = cal.get(Calendar.HOUR);

        cal.set(Calendar.HOUR, 0);
        cal.set(Calendar.MINUTE, 0);
        cal.set(Calendar.SECOND, 0);
        cal.set(Calendar.MILLISECOND, 0);

        boolean after0600 = startHour >=6 && start.getTime() % 60000 > 0;
        if(after0600) {
            cal.add(Calendar.DATE, 1);
        }
        return cal.getTimeInMillis();
    }

    public static boolean dateRangeTouches0200to0600(Date start, Date end) {
        boolean toReturn = false;
        long duration = end.getTime() - start.getTime();
        if(tripLongerThanTwentyHours(duration)) {
            toReturn = true;
        }
        else {
            long truncTestDate = getTruncDateFor0200And0600(start);
            long oh200 = truncTestDate + MS_IN_TWO_HOURS;
            long oh600 = truncTestDate + MS_IN_SIX_HOURS;
            long mustStart = oh200 - duration;
            long mustEnd = oh600 + duration;
            toReturn = start.getTime() >= mustStart && end.getTime() <= mustEnd;
        }
        return toReturn;
    }
}

public class OverlappingDateRangeUtilTest {

    private DateFormat dateTimeFormat;

    @Before
    public void setUp() throws Exception {
        dateTimeFormat = new SimpleDateFormat("MM/dd/yyyy HH:mm:ss");
    }

    @Test
    public void testDateRangeTouches0200to0600() throws ParseException {
        Date trip1Start = dateTimeFormat.parse("01/01/2017 00:15:00");
        Date trip1End = dateTimeFormat.parse("01/03/2017 01:45:00");
        assertTrue(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip1Start, trip1End));

        Date trip2Start = dateTimeFormat.parse("01/04/2017 13:00:00");
        Date trip2End = dateTimeFormat.parse("01/05/2017 13:00:00");
        assertTrue(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip2Start, trip2End));

        Date trip3Start = dateTimeFormat.parse("01/06/2017 00:00:00");
        Date trip3End = dateTimeFormat.parse("01/06/2017 05:00:00");
        assertTrue(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip3Start, trip3End));

        Date trip4Start = dateTimeFormat.parse("01/06/2017 06:01:00");
        Date trip4End = dateTimeFormat.parse("01/06/2017 23:00:00");
        assertFalse(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip4Start, trip4End));

        Date trip5Start = dateTimeFormat.parse("01/06/2017 06:01:00");      
        Date trip5End = dateTimeFormat.parse("01/06/2017 06:01:00");
        assertFalse(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip5Start, trip5End));

        Date trip6Start = dateTimeFormat.parse("01/06/2017 04:00:00");      
        Date trip6End = dateTimeFormat.parse("01/06/2017 04:00:00");
        assertTrue(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip6Start, trip6End));

        Date trip7Start = dateTimeFormat.parse("01/06/2017 03:00:00");      
        Date trip7End = dateTimeFormat.parse("01/06/2017 04:00:00");
        assertTrue(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip7Start, trip7End));

        Date trip8Start = dateTimeFormat.parse("01/06/2017 00:00:00");      
        Date trip8End = dateTimeFormat.parse("01/06/2017 01:30:00");
        assertFalse(OverlappingDateRangeUtil.dateRangeTouches0200to0600(trip8Start, trip8End));
    }

}
1
  • This is similar to what i tried. Only thing i can add is for people who wondering from where did 20 came from (its 24 -( 6-2)). That way we can keep the flexibility of having 6 and 2 as configurations as well. @Jon Sampson As you said, feels a little too much.
    – RBz
    Feb 5, 2017 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.