Как уменьшить количество потребляемой памяти скрипта, вычисляющего суммарную длину перекрывающихся интервалов?

Question

[rillkoff]

Решаю задачу на codewars: дан массив массивов, в которых записаны различные интервалы, требуется посчитать длину всех интервалов, за вычетом перекрывающих друг друга. Пробовал решить задачу через new Set() и через массивы, но и так, и так получается ошибка:

<--- Last few GCs --->

[1:0x7fb0ba8fb2d0]     2027 ms: Scavenge 1153.5 (1186.9) -> 1153.5 (1186.9) MB, 51.4 / 0.0 ms  (average mu = 1.000, current mu = 1.000) allocation failure 
[1:0x7fb0ba8fb2d0]     3094 ms: Mark-sweep 1727.3 (1760.7) -> 1721.5 (1756.2) MB, 388.8 / 0.0 ms  (+ 35.6 ms in 12 steps since start of marking, biggest step 4.6 ms, walltime since start of marking 2436 ms) (average mu = 1.000, current mu = 1.000) allocat

<--- JS stacktrace --->

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

Вот два варианта решения:

1 вариант:

const sumIntervals = (intervals) => {
    let setOut = new Set()
    let out = []
    intervals.forEach(element => {
        for (let i = element[0]; i < element[1]; ++i) {
            setOut.add(i)
        }
      
    });
    return (setOut.size)
}

2 вариант:

const sumIntervals = (intervals) => {
    let out = []
    intervals.forEach(element => {
        for (let i = element[0]; i < element[1]; i++) {
            out.push(i)
        }
    });
    out = out.sort();
    let result = out.filter((item, index, array) => {
        return array[index] != array[index + 1]
    })
    return result.length
}

Comments

[Дмитрий]

Так вы не набивайте массив по новой, а считайте без присвоения

[rillkoff]

Дмитрий, это Вы про out = out.sort();?

[User]

На js заставляют экономить память?!?

[Дмитрий]

rillkoff, out.push(i)
И про сорт тоже

[Дмитрий]

User, разве это плохо?)

[rillkoff]

Дмитрий, pushже просто добавляет в конец массива значение, он не перебирает его и не должен жрать память от слова совсем, разве нет?

[User]

Дмитрий, Обычно же всем плевать на клиента...

[Дмитрий]

rillkoff, вы из одного массива сохраняете в другом

Answer 1

[0xD34F]

Очевидно, надо написать какой-нибудь другой скрипт.

Объединяем перекрывающиеся интервалы, после объединения суммируем длины:

const sumIntervals = intervals => intervals
  .slice()
  .sort((a, b) => a[0] - b[0])
  .reduce((acc, n) => {
    const top = acc.at(-1);

    if (!top || top[1] < n[0]) {
      acc.push([...n]);
    } else if (top[1] < n[1]) {
      top[1] = n[1];
    }

    return acc;
  }, [])
  .reduce((acc, n) => acc - n[0] + n[1], 0);

Comments

[rillkoff]

Очевидно-то очевидно, проблема была придумать его) Спасибо, буду сидеть разбираться теперь что к чему там

[rillkoff]

Интересно, что при решении на Python, вариант с Set вполне себе рабочий и пишется в пару строк, не ругаясь на память