Interval range insert into intervals without merging existing intervals

user_261783 0
Viewed 87

Problem description: The idea is to insert into existing intervals new interval which doesn't merge with existing intervals but fills the missing gaps between intervals. (This is not the interval merging problem)

For example, inserting interval [0, 7] to intervals [[0, 1], [3, 5]] would result new intervals with gaps filled [[0, 1], [1, 3], [3, 5], [5, 7]].

Interval range is already sorted smallest to larger [[0, 1], [3, 5]].

My current solution is a bit "broken", I ended up using too many if checks to cover some special cases which makes everything more complex then needed. I am looking for better ways to simplify the condition part. In the bottom of the code there are test cases included, also cases where my solution fails.

The test cases where my algorithm is failing and producing wrong results:

assert.deepEqual( // Broken
    insertIntervalSec([[1, 5], [7, 10]], [4, 12]),
    [[1, 5], [5, 7], [7, 10], [10, 12]],
);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 3]), [[1, 3]]); // Broken

function isOverLapping(a, b) {
    return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
}

function insertIntervalSec(arr, interval) {
    const result = [];
    let i = 0;

    const contains = (a, b) => {
        return a[0] >= b[0] && a[1] <= b[1]
    };

    if (arr.length <= 0) {
        result.push(interval);
        return result;
    }
    if (arr.length === 1 && contains(interval, arr[0])) {
        result.push(interval);
        return result;
    }

    // Start point
    if (interval[1] >= arr[0][0] && isOverLapping(interval, arr[0])) {
        result.push([interval[0], arr[0][0]]);
    } else if (interval[1] <= arr[0][0]) {
        result.push([interval[0], Math.min(interval[1], arr[0][0])]);
    }

    while (i < arr.length) {
        const current = arr[i];
        result.push(arr[i]);

        if (!contains(interval, arr[i]) && isOverLapping(arr[i], interval)) {
            const next = arr[i + 1];

            // Special handling for the last item
            if (next !== undefined) {
                if (interval[1] > current[1]) {
                    result.push([current[1], next[0]]);
                }
            } else {
                if (interval[0] <= current[0] && interval[1] <= current[1]) {
                    // TODO: No action
                } else if (interval[0] >= current[0] || interval[1] >= current[0]) {
                    result.push([current[1], interval[1]]);
                }
            }
        }
        i++;
    }

    // End point
    const len = arr.length;
    const last = arr[len - 1];
    if (last[1] <= interval[0] && !isOverLapping(last, interval)) {
        result.push(interval);
    }

    return result;
}

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [12, 27]),
    [[1, 5], [10, 15], [15, 20], [20, 25], [25, 27]]
);

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [-3, 0]),
    [[-3, 0], [1, 5], [10, 15], [20, 25]]
);

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [-3, 3]),
    [[-3, 1], [1, 5], [10, 15], [20, 25]]
);

assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [15, 15]),
    [[0, 5], [10, 15], [20, 25]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [20, 21]),
    [[0, 5], [10, 15], [20, 25]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [26, 27]),
    [[0, 5], [10, 15], [20, 25], [26, 27]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [25, 27]),
    [[0, 5], [10, 15], [20, 25], [25, 27]]
);
assert.deepEqual(insertIntervalSec([], [25, 27]), [[25, 27]]);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 1]), [[1, 1]]);
assert.deepEqual( // Broken
    insertIntervalSec([[1, 5], [7, 10]], [4, 12]),
    [[1, 5], [5, 7], [7, 10], [10, 12]],
);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 3]), [[1, 3]]); // Broken

assert.deepEqual(
    insertIntervalSec2([[5, 5]], [6, 6]),
    [[5, 5], [6, 6]]
);

assert.deepEqual(
    insertIntervalSec2([[1, 3]], [6, 6]),
    [[1, 3], [6, 6]]
);
algorithm javascript
1 Answers

With the exception of the last test case (see comment on question), this passes all the tests. The basic idea is you just keep track of start variable that indicated where how much of the inserted range you have used. This allows you to narrow it down to three cases:

  1. the inserted interval fits entirely before the the current item
  2. the current item in the iteration fits completely before the inserted interval
  3. the item in the iteration overlaps.

After iterating the items, you can check if the inserted range has anything left to insert:

function insertIntervalSec(arr, insert) {
  let start = insert[0]
  let res = []
  for (i = 0; i < arr.length; i++) {
    let a = arr[i]
    // smaller item in range
    if (a[0] <= start) {
      res.push(a)
      start = Math.max(a[1], start)
      continue
    }
    // moved past inserted interval add rest of arr
    if (start >= insert[1]) {
      res.push(...arr.splice(i))
      break
    }

    // fill in spaces
    let end = Math.min(insert[1], a[0])
    res.push([start, end], a)
    start = a[1]
  }
  // clean up left over range
  if (start < insert[1]) res.push([start, insert[1]])

  return res
}

console.log(insertIntervalSec([ [1, 5],[10, 15],[20, 25]], [-2, 27]))

user_38746230
Related