Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 1x 4x 4x 4x 4x 4x 4x 11x 11x 11x 11x 11x 13x 13x 13x 4x 4x 4x 13x 13x 11x 11x 7x 7x 11x 4x 4x 4x 1x 1x 3x 3x 3x 3x 3x 8x 8x 8x 8x 8x 8x 8x 3x 3x 3x 3x 3x 3x 3x 3x 3x 10x 10x 10x 10x 4x 4x 3x 3x 3x 3x 1x 1x | // Given a list of intervals: [s, el for meetings.
// Find the least number of meeting rooms required.
// • Constraints:
// • 1 < N < 1e5
// • 1 ≤ A[i] [0] < A[i] [1] < 1e9
// Input: [[5, 10], [15,20], [0,30]]
// Output: 2
// Explanation:
// [0,30] and [5, 10] take place simultaneously
// Same for [0,30] and [15, 20]
const meetingRoom = (intervals: number[][]): number => {
const intervalsSorted = intervals.sort(
(first, second) => first[0] - second[0]
);
const rooms = [];
for (let x = 0; x < intervalsSorted.length; x++) {
const interval = intervalsSorted[x];
let found = false;
let i = 0;
// find room
while (i < rooms.length && !found) {
const room = rooms[i];
// check if found
if (room[1] <= interval[0]) {
found = true;
room[1] = interval[1];
}
i++;
}
if (!found) {
rooms.push(interval);
}
}
return rooms.length;
};
export const meetingRoom2 = (intervals: number[][]): number => {
let max = 0;
// [[5, 10], [15, 20]] -> {5: 1, 10: -1, 15: 1, 20: -2};
const intervalByKey = intervals.reduce<Record<string, number>>(
(acc, current) => {
const [start, end] = current;
acc[start] = (acc[start] || 0) + 1;
acc[end] = (acc[end] || 0) - 1;
return acc;
},
{}
);
const keysSorted = Object.keys(intervalByKey).sort(
(a, b) => Number(a) - Number(b)
);
let currentRoom = 0;
keysSorted.forEach((time) => {
const numberOfRoom = intervalByKey[time];
currentRoom += numberOfRoom;
if (currentRoom > max) {
max = currentRoom;
}
});
return max;
};
export default meetingRoom;
|