Problem statement is as follows
Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.
For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.
This is supposed to be an easy challenge but it was not the case for me.
Here is my solution in JavaScript
// Given an array of time intervals (start, end) for classroom lectures (possibly overlapping),
// find the minimum number of rooms required.
// For example, given [(30, 75), (0, 50), (60, 150)], you should return 2.
exports.roomsRequired = function roomsRequired(lectureIntervals) {
function Room() {return {busy: []};}
let rooms = [];
lectureIntervals.forEach(lectureInterval => {
let roomFound = false;
rooms.forEach(room => {
let roomBusyInLectureHours = false;
room.busy.forEach(reserved => {
if (lectureInterval[0] > reserved[0] && lectureInterval[0] < reserved[1]) roomBusyInLectureHours = true;
if (lectureInterval[1] > reserved[0] && lectureInterval[1] < reserved[1]) roomBusyInLectureHours = true;
if (reserved[0] > lectureInterval[0] && reserved[0] < lectureInterval[1]) roomBusyInLectureHours = true;
if (reserved[1] > lectureInterval[0] && reserved[1] < lectureInterval[1]) roomBusyInLectureHours = true;
});
if (!roomBusyInLectureHours) {
room.busy.push(lectureInterval);
roomFound = true;
}
});
if (!roomFound) {
let room = new Room();
room.busy.push(lectureInterval);
rooms.push(room);
}
});
return rooms;
};
The only test case I have so far
let rooms = exports.roomsRequired([[30, 75], [0, 50], [60, 150]]);
for (let i = 0; i < rooms.length; i++) {
console.log(rooms[i].busy)
}
Which prints
[ [ 30, 75 ] ]
[ [ 0, 50 ], [ 60, 150 ] ]
I am aware that I am not returning the number of rooms, but that is essentially the number of rows seen, so for example in the case above it is 2
as expected.
My question is, can this code be much shorter? I suspect I am missing something obvious being this challenge easy.
Pseudo code of my implementation would be something like this
For Each Interval:
For Each Room in Rooms:
For Each IntervalWithinThatRoom:
Check If IntervalWithinThatRoom overlaps with Interval
If No Overlaps Found
Push Interval to Room
If Interval Not pushed to any Room
Create new Room
Push Interval to Room
Push new Room to Rooms
Edit - Unit Tests I have
expect(roomsRequired.roomsRequired([[30, 75], [0, 50], [60, 150]]).length).eq(2);
expect(roomsRequired.roomsRequired([[5, 7], [0, 9], [5, 9]]).length).eq(3);
a
,b
,c
, ... as variable names, remove spaces and newlines. I think I know what you mean, but can you phrase it more precisely? \$\endgroup\$[[5, 7], [0, 9], [5, 9]]
your function returns an array of 2 rooms, however the times all overlap and thus require 3 room to be concurrent. Your overlap logic is at fault (guess from a quick look). Unfortunately questions need working code to be reviewed... :) \$\endgroup\$I am aware that I am not returning the number of rooms, but that is essentially the number of rows seen
What I am trying to ask is, is there a way to do it shorter in terms of time complexity, not source code length. @ThomasWeller \$\endgroup\$