CODEWITHSUNDEEP
javaalgorithmrange
avee
avee

Reputation: 776

How to calculate that no sub range overlap each other and all sub range covers whole range in java?

I have a range in java implemented as a class which is divided into sub-ranges. The implementation is roughly as follows:

public class Range
{
   static public class Key implements Comparable<Key>
   {
      public int start;
      public int end;
      ...
   }

   Key range;
   SortedMap<Key, Range> subRange;
}

I want to make a function that makes sure that no subrange overlaps each other and the combined range of the subrange covers total range completely. Start and end of each range may be equal.

Example of a valid object:

Range: start 1, end 10
  subrange 1: start 1, end 2
  subrange 2: start 3, end 9
  subrange 3: start 10, end 10

What would be the best way to implement this?

EDIT:

To anyone interested in the implementation:

In my validation code I do these steps:

  1. Convert the sorted map to an Array
  2. Force the first and last element to cover the beginning and end of total range
  3. Iterate array elements and fix gaps or overlap between them

Code for step 3:

for (int i=0; i < (rangeArray.length - 1); i++)
{
    if (rangeArray[i].range.end < (rangeArray[i+1].range.start - 1) ||
        rangeArray[i].range.end >= rangeArray[i+1].range.start)
    {
        // Alternatively, lose the if and just force subrange to behave this way
        rangeArray[i].range.end = rangeArray[i+1].range.start - 1; 
    }
}

Upvotes: 1

Views: 954

Answers (2)

user1732055
user1732055

Reputation: 2507

Another way to do it is to do the sum of all the ranges and compare it to the delta of the maximum and minimum values across all ranges. If the sum is greater or equal to the delta, that means there's intersection.

Upvotes: 2

tangens
tangens

Reputation: 39733

Since your subRange map is sorted, you can iterate over it and check that there is no gap in the sequence of end to the next start. And of course from your total starting point to the first start and your last end to your total ending point. Apply this check recursively to all subRanges, too.

For this your map has to be sorted by start, which is the case in your example.

Upvotes: 3

Related Questions