Get number range intersection

Question

In addition to this question Find number range intersection I want to get the intersection range of 2 time ranges. So my question is

What is the efficient mathematical/algorithmic way to get the time range of the intersection of two number ranges ?

Did you want the intersection or the union? – Ignacio Vazquez-Abrams Mar 22 '11 at 12:50 — Ignacio Vazquez-Abrams, Mar 22 '11 at 12:50
Intersection sorry (post edited) – Manuel Selva Mar 22 '11 at 12:58 — Manuel Selva, Mar 22 '11 at 12:58

score 2 · Accepted Answer · answered Mar 22 '11 at 12:58

    public BTraceStatsTimeRange getOverlap(BTraceStatsTimeRange other) {
    if (!intersect(other)) {
        return NULL;
    }
    long startOther = other.start;
    long endOther = other.end;
    long minEnd = Math.min(end, endOther);
    long maxStart = Math.max(start, startOther);
    return new BTraceStatsTimeRange(Math.min(minEnd, maxStart), Math.max(
            minEnd, maxStart));
}

I am tired today .... ;-)

score 2 · Answer 2 · answered Mar 22 '11 at 17:00

This pseudo-C should do the trick:

R_TYPE Intersection(P_TYPE start1, P_TYPE start2, P_TYPE end1, P_TYPE end2)
{

    if(max(start1, start2) <= min(end1, end2))
    {
        return( min(end1, end2) - max(start1, start2) );
    }

    return(DISJOINT);
}

R_TYPE is your 'custom' return type, P_TYPE is your 'custom' parameter type. You can set them to any valid signed scalar number type (int, float, etc.) Use #define DISJOINT ... to set DISJOINT to some value that would normally be out of range (-1 or MAX_INT, etc.)

If you have some custom DATE_TIME_TYPE, you'll have to change this to accommodate that. For instance, if you define a struct like:

typedef union
{
    unsigned char date_time[7];
    struct
    {
        unsigned char second;
        unsigned char minute;
        unsigned char hour;
        unsigned char day;
        unsigned char month;
        unsigned int  year;
    }
}DATE_TIME_TYPE;

You might still be able to get by doing a straight comparison between values (assuming little-endian and 8-bit addressing), but you'll have to account for carries and underflow when subtracting individual days, minutes, etc.

score 0 · Answer 3 · answered Jun 17 '15 at 21:26

0

If someone needs the javascript version is here:

function findRangeIntersection(a1, a2, b1, b2) {
    if (Math.max(a1, b1) <= Math.min(b2, a2)) {
        return Math.min(a2, b2) - Math.max(a1, b1);
    }
    return Number.NaN;
}

answered Jun 17 '15 at 21:26

CodeArtist

5,534
8
40
65

Ignacio Vazquez-Abrams · Answer 4 · 2011-03-22T13:23:08.303

Subtract each of the endpoints of the first range from each of the endpoints of the second range. If you have:

All positive or negative results: the ranges are disjoint
One non-negative or negative result: the intersection is the operands for this result
Two non-negative results: the range is the non-common operand in both calculations

All results are 0: the most degenerate ranges ever

vectors = (
  ((1, 3), (2, 4), '2-3'),
  ((1, 4), (2, 3), '2-3'),
  ((1, 2), (3, 4), 'Disjoint'),
  ((2, 4), (1, 3), '2-3'),
  ((2, 3), (1, 4), '2-3'),
  ((3, 4), (1, 2), 'Disjoint'),
)

for a, b, c in vectors:
  print c, a, b
  for x in a:
    for y in b:
      print x, y, x-y

Get number range intersection

4 Answers4