CODEWITHSUNDEEP
algorithmmath
Manuel Selva
Manuel Selva

Reputation: 19050

Get number range intersection

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 ?

Upvotes: 1

Views: 1355

Answers (4)

CodeArtist
CodeArtist

Reputation: 5714

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

Upvotes: 0

oosterwal
oosterwal

Reputation: 1479

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.

Upvotes: 2

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 799550

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

Upvotes: 0

Manuel Selva
Manuel Selva

Reputation: 19050

    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 .... ;-)

Upvotes: 2

Related Questions