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

[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)

[рони]

:) :write:
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,
:thanks: