Есть ли более элегантное решение для получения инверсии массива диапазонов?

Question

Давайте представим следующее:

У вас есть строка, которая начинается с 1 и заканчивается на 10000.

Вам дан массив диапазонов, таких как [{ start: 5, end: 10 }, { start: 15, end: 25 }]

Учитывая массив диапазонов, найти обратное.

Для приведенного выше примера обратное будет [{ start: 1, end: 4 }, { start: 11, end: 14 }, { start: 26, end: 10000 }]

Обратите внимание, что инверсия - это практически все остальные диапазоны на нашей линии.

Ниже мое текущее решение ... Есть ли более элегантное решение, которое не должно явно иметь дело с крайними случаями?

Обратите внимание, в моем коде диапазоны именуются регионами.

const inverseRegions = (regions) => {

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

  let result = []

  // 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.push({
      start: 1,
      end: regions[0].start - 1
    })
  }

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

Ожидаемые результаты:

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

Answer 1

Вы можете использовать reduce, инициализированный аккумулятором, который содержит весь регион, а затем разделить этот последний регион, когда вы столкнетесь с новыми диапазонами:

function inverseRegions(ranges) {
  return ranges.reduce((acc, curr) => {
    let prev = acc.pop();
    if (curr.start > prev.start) 
      acc.push({start: prev.start, end: curr.start - 1})
    if (prev.end > curr.end)
      acc.push({start: curr.end + 1, end: prev.end});
    return acc;
  }, [{start: 1, end: 10000}])
}


console.log(inverseRegions([{ start: 5, end: 10 }, { start: 15, end: 25 }]));
console.log(inverseRegions([]));
console.log(inverseRegions([{ start: 1, end: 10 }, { start: 15, end: 20 }]));
console.log(inverseRegions([{ start: 5, end: 10 }, { start: 12, end: 60 }, { start: 66, end: 10000 }])); 
console.log(inverseRegions([{ start: 8, end: 12 }, { start: 16, end: 20 }, { start: 29, end: 51 }]));

Это, конечно, предполагает, что ваши интервалы отсортированы.