Give you set of meetings start time and end time, count how many meeting rooms needed.
For example:
[[, ], [, ], [, ], [, ]] // needs 3 meeting rooms
We can use a memo table to store the at which time how many rooms needed. It is sort of like Knapsack problem. Check out this post for similar question.
Code:
function* generateAry(start, end) {
let i = start;
while (i <= end) {
yield i;
i++;
}
}
// O(N*K): K: number of hours, N: number of room
// S(K)
function availableRoom(arys) {const { min, max } = arys.reduce(
(acc, ary) => {
const [start, end] = ary;
let { min, max } = acc;
if (start < min) {
min = start;
}
if (end > max) {
max = end;
}
return { min, max };
},
{ min: Infinity, max: }
);
const hours = Array.from(generateAry(min, max));
const memo = hours.map(x => );
function helper(arys, hours, memo) {
let countRooms = ;
for (let row in arys) {
for (let col in hours) {
let prevCount = memo[col];
let [min, max] = arys[row];
// if the min > hour, set previous row same col value, the same as max < hour
if (min > hours[col] || max < hours[col]) {
memo[col] = prevCount;
continue;
}
if (min <= hours[col] && max >= hours[col]) {
memo[col] = prevCount + ;
}
countRooms = Math.max(countRooms, memo[col]);
}
}
console.log(memo); // [1, 3, 3, 2, 2, 2, 2, 1]
return countRooms;
}
return helper(arys, hours, memo);
}
console.log(availableRoom([[, ], [, ], [, ], [, ]])); // 3