Задача про отель

[dc65k]

Всем привет. Подскажите, верно ли я решил данную задачу?

/*
Даны даты заезда и отъезда каждого гостя.
Для каждого гостя дата заезда строго раньше даты отъезда (то есть каждый гость останавливается хотя бы на одну ночь).
В пределах одного дня считается, что сначала старые гости выезжают, а затем въезжают новые. Найти максимальное число постояльцев, которые одновременно проживали в гостинице (считаем, что измерение количества постояльцев происходит в конце дня).
 */

const dates = [
    [1, 2],
    [1, 3],
    [2, 4],
    [2, 3],
]

const f = (arr) => {

    let acc = 0;

    let arrivalDate = arr.reduce((accumulator, currentValue) => {

        let key = currentValue[0]

        if (accumulator[key]) {
            accumulator[key] += 1
        } else {
            accumulator[key] = 1
        }

        return accumulator
    }, {});

    let departureDate = arr.reduce((accumulator, currentValue) => {

        let key = currentValue[1]

        if (accumulator[key]) {
            accumulator[key] += 1
        } else {
            accumulator[key] = 1
        }

        return accumulator
    }, {});

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

        let current = arr[i];

        acc -= departureDate[current[1]];
        acc += arrivalDate[current[0]];
    }

    return acc;
}

console.log(f(dates));

[ksa]

Предложу такой вариант...

const dt = [
    [1, 2],
    [1, 3],
    [2, 4],
    [2, 3],
]
let min = dt[0][0]
let max = dt[0][0]
dt.forEach(el => {
	min = Math.min(min, el[0])
	max = Math.max(max, el[1])
})
let t = 0
for (let i = min; i <= max; i++) {
	let c = 0
	dt.forEach(el => {
		if ((el[0] <= i) && (i < el[1])) ++c
	})
	alert(i + ' - ' + c)
	t = Math.max(t, c)
}
alert(t)

[рони]

const dt = [
    [1, 2],
    [1, 3],
    [2, 4],
    [2, 3]
]
let arr = dt.flat();
let min = Math.min(...arr);
let max = Math.max(...arr);

let t = 0;
for (let i = min; i <= max; i++) {
	let c = 0;
	dt.forEach(el => {
		if ((el[0] <= i) && (i < el[1])) ++c
	})
	alert(i + ' - ' + c)
	t = Math.max(t, c)
}
alert(t)

const dt = [
            [1, 2],
            [1, 3],
            [2, 4],
            [2, 3]
        ]
        let arr = dt.map(([a, b]) => Array.from({
            length: b - a
        }, (_, i) => a + i)).flat().sort((a, b) => a - b);

        let c = 0,
            t = 0,
            n;
        for (let i of arr) {
            if (i === n) c++;
            else {
                c = 1;
                n = i;
            }
            if (c > t) t = c;

        }

        alert(t)

[Alexandroppolus]

Math.min(...arr)

на здоровенном массиве это свалится в переполнение стека.

----
мой вариант:

function getMaxCount(dates) {
    const sortedByBegin = dates.slice().sort((a, b) => a[0] - b[0]);
    const ends = dates.map(d => d[1]).sort((a, b) => a - b);

    let count = 0, endPos = 0;
    return sortedByBegin.reduce((max, date, i) => {
        // учитываем все выезды, которые были после предыдущей проверки
        while (endPos < ends.length && ends[endPos] <= date[0]) {
            count--;
            endPos++;
        }

        return Math.max(max, ++count);
    }, 0);
}

alert(getMaxCount([
    [1, 2],
    [1, 3],
    [2, 4],
    [2, 3]
]));

работает за O(N * ln(N)) времени и O(N) памяти, но при этом не закладывается на максимальные даты, плюс можно применить например для отрезков, у которых начало и конец вещественные. Универсально, в общем.

если интервалы уже отсортированы по дате заезда, то вторую строку лучше переписать так

const sortedByBegin = dates;

[рони]

Alexandroppolus,