educative.io

Educative

Actual Solution

Like Lakshay pointed out here Recommended additional test case the provided solution doesn’t cover all considered cases according to the problem.

Here’s a complete solution for the problem:

class Interval {

  constructor(start, end) {

    this.start = start;

    this.end = end;

  }

  print_interval() {

    process.stdout.write(`[${this.start}, ${this.end}]`);

  }

}

const merge = function (intervals_a, intervals_b) {

  let result = []

  let indexA = 0

  let indexB = 0

  while (indexA < intervals_a.length && indexB < intervals_b.length) {

    // We're only finished when we reach the end of both lists

    // so we need to make sure we don't overflow the indexes.

    let cappedIndexA = Math.min(intervals_a.length - 1, indexA)

    let cappedIndexB = Math.min(intervals_b.length - 1, indexB)

   

    let intervalA = intervals_a[cappedIndexA]

    let intervalB = intervals_b[cappedIndexB]

    // interval B is in front of interval A (no overlap)

    // move to next interval A

    if (intervalA.end < intervalB.start) {

      indexA += 1

      continue

    }

    // interval B is behind interval A (no overlap)

    // move to next interval B

    if (intervalB.end < intervalA.start) {

      indexB += 1

      continue

    }

    // push the overlapping interval

    const overlapStart = Math.max(intervalA.start, intervalB.start)

    const overlapEnd = Math.min(intervalA.end, intervalB.end)

    result.push(new Interval(overlapStart, overlapEnd))

    // step iteration forward

    if (intervalA.end < intervalB.end) {

      indexA += 1

    } else {

      indexB += 1

    }

  }

  return result

};

process.stdout.write('Intervals Intersection: ');

let result = merge([new Interval(1, 3), new Interval(5, 6), new Interval(7, 9)], [new Interval(2, 3), new Interval(5, 7)]);

for (i = 0; i < result.length; i++) {

  result[i].print_interval();

}

console.log()

console.log("------------- Expected: [2, 3][5, 6][7, 7]");

process.stdout.write('Intervals Intersection: ');

result = merge([new Interval(1, 3), new Interval(5, 7), new Interval(9, 12)], [new Interval(5, 10)]);

for (i = 0; i < result.length; i++) {

  result[i].print_interval();

}

console.log()

console.log("------------- Expected: [5, 7][9, 10]");

process.stdout.write('Intervals Intersection: ');

result = merge(

  [new Interval(0, 2), new Interval(5, 10), new Interval(13, 23), new Interval(24, 25)],

  [new Interval(1, 5), new Interval(8, 12), new Interval(15, 24), new Interval(25, 26)]

);

for (i = 0; i < result.length; i++) {

  result[i].print_interval();

}

console.log()

console.log("------------- Expected: [1, 2][5, 5][8, 10][15, 23][24, 24][25, 25]");

Type your question above this line.
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6518042546667520

Hi @Nicolas_F
Thank you for your suggestion regarding the betterment of code. We’ll look into it. Your feedback is much appreciated!