Is there a more elegant solution to getting the inverse of an array of ranges?

2095 views javascript
0

Let's imagine the following:

You have a line that starts at 1 and ends at 10000.

You're given an array of ranges like [{ start: 5, end: 10 }, { start: 15, end: 25 }]

Given an array of ranges, find the inverse.

For the above example, the inverse would be [{ start: 1, end: 4 }, { start: 11, end: 14 }, { start: 26, end: 10000 }]

Notice how the inverse is basically every other range on our line.

Below is my current solution... Is there a more elegant solution that doesn't have to explicitly deal with the edge cases?

Note, in my code ranges are named regions.

const inverseRegions = (regions) => {

  // If no regions, the inverse is the entire line.
  if (regions.length === 0) { 
    return [{ start: 1, end: 10000 }] 
  }

  let result = []

  for (let i = 1; i < regions.length; i++) {
    const previousRegion = regions[i-1]
    const region = regions[i]

    result.push({
      start: previousRegion.end + 1,
      end: region.start - 1
    })
  }

  // If the first region doesn't start at the beginning of the line
  // we need to account for the region from the 1 to the start of
  // first region
  if (regions[0].start !== 1) {
    result.unshift({
      start: 1,
      end: regions[0].start - 1
    })
  }

  // If the last region doesn't end at the end of the line
  // we need to account for the region from the end of the last
  // region to 10000
  if (regions[regions.length - 1].end !== 10000) {
    result.push({
      start: regions[regions.length - 1].end + 1,
      end: 10000
    })
  }

  return result
}

Expected results:

inverseRegions([]) 
  => [ { start: 1, end: 10000 } ]

inverseRegions([{ start: 1, end: 10 }, { start: 15, end: 20 }]) 
  => [ { start: 11, end: 14 }, 
       { start: 21, end: 10000 } ]

inverseRegions([{ start: 5, end: 10 }, { start: 12, end: 60 }, { start: 66, end: 10000 }]) 
  => [ { start: 1, end: 4 },
       { start: 11, end: 11 },
       { start: 61, end: 65 } ]

inverseRegions([{ start: 8, end: 12 }, { start: 16, end: 20 }, { start: 29, end: 51 }]) 
  => [ { start: 1, end: 7 },
       { start: 13, end: 15 },
       { start: 21, end: 28 },
       { start: 52, end: 10000 } ]

answered question

1 Answer

10

I describe algorithm suitable for unsorted intervals with overlapping.

If your intervals always are sorted and overlapping is not possible, ignore sorting step and creating explicit pair with flag.

But fictive ends concept + opening/closing output intervals depending on start/end of source might be useful.


Make an array/list containing pairs {interval_start or interval_end; Flag = +1 for start/ -1 for end}

Add two fictive points {0;-1} and {10000;+1} to provide uniform treatment. Now list contains 2n+2 items.

Sort this list by the first field. In case of tie use Flag (place +1 item first)

Make ActiveCnt = 1

Traverse list in order, at every step add Flag to ActiveCnt

When ActiveCnt becomes zero, open output interval, remember start position

When ActiveCnt becomes non-zero, closes output interval, add it to result

posted this

Have an answer?

JD

Please login first before posting an answer.