найти недостающий диапазон в заданном диапазоне

Question

Нам нужно найти пропущенный диапазон, когда задан основной диапазон и заданы все поддиапазоны. основной диапазон: [- 10, 10]

поддиапазоны: [-10, -5], [-4, -3], [-2, 3], [7, 10]

Допущения:

1) Значения диапазона могут go до 2 ^ 63.

2) поддиапазоны не будут перекрываться, и их порядок может отличаться. Например: может быть [-10, -5], [7, 10], [-2, 3], [-4, -3]

, что является лучшим алгоритмом для поиска недостающего диапазона здесь

Answer 1

Предполагая, что интервалы не отсортированы, я не вижу возможности избежать затрат на сортировку, поскольку каждый интервал может быть одиночным ([n,n]). Эта стоимость может быть O(n log n) для сортировки сравнения или O(n) для сортировки по основанию. Теперь давайте предположим, что входные интервалы отсортированы и не содержат перекрытий. Вот реализация O(n) single pass Python:

xs =  [[-10, -5] , [-4, -3], [-2, 3], [7, 10]]
bounds = (-10, 10)
missing = list()

# pre-processing
xs_sorted = sorted(xs)

# pre-processing a missing range on the lower bound
if bounds[0] < xs_sorted[0][0]:
  missing.append((bounds[0], xs_sorted[0][0]-1))

def f_reduce(a, b):
  if a[1] + 1 == b[0]:
    # merge contiguous intervals
    return (a[0], b[1])
  else:
    # gap detected; add the gap to the missing range list
    # and move to the next value
    missing.append((a[1]+1, b[0]-1))
    return b

from functools import reduce
reduce(f_reduce, xs_sorted)

# post-processing on a missing range on the upper bound
if bounds[1] > xs_sorted[-1][1]:
  missing.append((xs_sorted[-1][1]+1, bounds[1]))

print(missing)
# [(4, 6)]

Подход заключается в использовании функционального стиля reduce с вонючим побочным эффектом. Когда функция f_reduce встречает два интервала (a, b) и (c, d), мы возвращаем составной интервал (a, d), если b + 1 == c. В противном случае, разрыв обнаруживается и сохраняется; возвращаемый интервал (c, d). Этапы предварительной и последующей обработки связаны с неприятными случаями, когда в двух крайних диапазонах интервала возникают пропуски.

Answer 2

Предполагая только один пропущенный интервал:

Мы можем сделать это в O (k), где k - число поддиапазонов.

Сделать цепочку (например, Chasles ) подключенных поддиапазонов (поскольку они тривиально не перекрываются).

В конце три возможных случая:

• только одна цепочка: отсутствующий поддиапазон находится в начале
• или в конце
• две цепочки: он находится между

В текущем подинтервале проверьте, является ли это продолжением цепочки.

• если не создать другую цепочку.
• если да, увеличить цепочку, как ssssnake. Тогда, возможно, он соединяет эту цепь с другой. Затем уменьшите две цепочки и подинтервал как одну большую цепочку.

. Цепочка может быть просто представлена ​​слева и справа. Чтобы найти цепочку для увеличения, можно просто использовать хэш-карту слева и еще один справа

function getMissingSub (subs, minRange, maxRange) {
  const chainsByLeft = new Map () // left -> [left, whatsoever]
  const chainsByRight = new Map () // right -> [whatsoever, right]
  // before: [[a, [a, whatsoever]]]
  // after: [[newVal, [newval, whatsoever]]]
  function prolongeLeft (x, newVal) {
    const chain = chainsByLeft.get(x)
    const old = chain[0]
    chain[0] = newVal
    chainsByLeft.set(newVal, chain)
    chainsByLeft.delete(old)
    return chain
  }
  function prolongeRight (x, newVal) {
    const chain = chainsByRight.get(x)
    const old = chain[1]
    chain[1] = newVal
    chainsByRight.set(newVal, chain)
    chainsByRight.delete(old)
    return chain
  }
  subs.forEach(([a,b]) => {
    if (chainsByLeft.has(b) || chainsByRight.has(a)) {
      if (chainsByLeft.has(b)) {
        // prolonge on the left
        const chain = prolongeLeft(b, a)
        if (chainsByRight.has(a) ) {
          prolongeRight(a, chain[1])
        }
      } else {
        const chain = prolongeRight(a, b)
        if (chainsByLeft.has(b) ) {
          prolongeLeft(b, chain[0])
        }
      }
    } else {
      // new chain
      const chain = [a, b]
      chainsByLeft.set(a, chain)
      chainsByRight.set(b, chain)
    }
  })
  let missingRange
  if (chainsByLeft.size === 1) {
    const [, [left, right]] = chainsByLeft.entries().next().value
    if (left === minRange) {
      missingRange = [right, maxRange]
    } else {
      missingRange = [minRange, left]
    }
  } else {
    const [[, [l1, r1]], [, [l2, r2]]] = chainsByLeft.entries()
    if (r1 < r2) {
      missingRange = [r1, l2]
    } else {
      missingRange = [r2, l1]
    }
  }
  return { missingRange, chainsByLeft }
}
const dump = ({ missingRange: [a,b] }) => console.log(`missing [${a}, ${b}]`)
dump(getMissingSub([[0, 1],[1, 2]], 0, 4))
dump(getMissingSub([[0, 1],[1, 2]], -1, 2))
dump(getMissingSub([[0, 1],[2, 3]], 0, 3))
dump(getMissingSub([[-10, -5] , [-4, -3], [-2, 3], [7, 10]], -10, 10))

---

Если у вас есть несколько пропущенных диапазонов, очевидно, вы можете иметь более двух цепочек, тогда вам может потребоваться сортировка, чтобы упорядочить цепочки и непосредственно найти разрыв между последовательные цепочки

//COPY PASTED FROM BEFORE
function getMissingSub (subs, minRange, maxRange) {
  const chainsByLeft = new Map () // left -> [left, whatsoever]
  const chainsByRight = new Map () // right -> [whatsoever, right]
  // before: [[a, [a, whatsoever]]]
  // after: [[newVal, [newval, whatsoever]]]
  function prolongeLeft (x, newVal) {
    const chain = chainsByLeft.get(x)
    const old = chain[0]
    chain[0] = newVal
    chainsByLeft.set(newVal, chain)
    chainsByLeft.delete(old)
    return chain
  }
  function prolongeRight (x, newVal) {
    const chain = chainsByRight.get(x)
    const old = chain[1]
    chain[1] = newVal
    chainsByRight.set(newVal, chain)
    chainsByRight.delete(old)
    return chain
  }
  subs.forEach(([a,b]) => {
    if (chainsByLeft.has(b) || chainsByRight.has(a)) {
      if (chainsByLeft.has(b)) {
        // prolonge on the left
        const chain = prolongeLeft(b, a)
        if (chainsByRight.has(a) ) {
          prolongeRight(a, chain[1])
        }
      } else {
        const chain = prolongeRight(a, b)
        if (chainsByLeft.has(b) ) {
          prolongeLeft(b, chain[0])
        }
      }
    } else {
      // new chain
      const chain = [a, b]
      chainsByLeft.set(a, chain)
      chainsByRight.set(b, chain)
    }
  })
  let missingRange
  if (chainsByLeft.size === 1) {
    const [, [left, right]] = chainsByLeft.entries().next().value
    if (left === minRange) {
      missingRange = [right, maxRange]
    } else {
      missingRange = [minRange, left]
    }
  } else {
    const [[, [l1, r1]], [, [l2, r2]]] = chainsByLeft.entries()
    if (r1 < r2) {
      missingRange = [r1, l2]
    } else {
      missingRange = [r2, l1]
    }
  }
  return { missingRange, chainsByLeft }
}

//ENDCOYP PASTED

function getMissingSubs(subs, minRange, maxRange) {
  const { missingRange, chainsByLeft } = getMissingSub.apply(null, arguments)
  const missingRanges = []
  ;[[minRange, minRange], ...chainsByLeft.values(), [maxRange, maxRange]]
    .sort((a,b) => a[0]-b[0]).reduce((chain, next) => {
      if (chain[1] !== next[0]) {
        missingRanges.push([chain[1], next[0]])
      }
      return next
    })
  return { missingRanges }
}
const dump2 = ({ missingRanges }) => console.log(`missing2 ${JSON.stringify(missingRanges)}`)
dump2(getMissingSubs([[0, 1],[1, 2]], 0, 4))
dump2(getMissingSubs([[0, 1],[1, 2]], -1, 2))
dump2(getMissingSubs([[0, 1],[2, 3]], 0, 3))
dump2(getMissingSubs([[-10, -5] , [-4, -3], [-2, 3], [7, 10]], -10, 10))

Answer 3

Похоже, вы можете пройти через массив и найти индекс i, где

xi != y(i-1)

Pair

(y(i-1), xi) 

- это ответ

Answer 4

Попробуйте использовать следующий способ, он работает в O (n), где n - ширина диапазона.

// entire range is initially 0.
    int arr[range_max - range_min + 2] = {0};
    //for each sub_range increment the values by 1.
    for(int i = 0; i<n; i++){
        arr[sub_range_min[i] - range_min] += 1;
        arr[sub_range_min[i] - range_max + 1] -= 1;
    }
    for(int i = 1; i< range_max - range_min + 2; i++){
        arr[i] += arr[i-1];
    }
    // all the uncovered area in the range by the sub_ranges will be marked 0 in the array.