5
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ You want it shorter? Use 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\$ – Thomas Weller Aug 18 at 1:41
  • \$\begingroup\$ Helps to test code first, Two problems , A: The question states "...find the minimum number..." yet your function returns an array of rooms, not a number? B: how many rooms needed to concurrency host times [[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\$ – Blindman67 Aug 18 at 12:37
  • \$\begingroup\$ @Blindman67 You are abs right, thank you. I fixed it (I think). I know it returns an array and I am fine with it, I slightly modified the problem statement in that regard, as I noted in my question. 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\$ – Koray Tugay Aug 18 at 14:32
  • 1
    \$\begingroup\$ Searching for "rooms" on this site brought me to this question, which looks very similar and has an interestingly simple solution. \$\endgroup\$ – Roland Illig Aug 18 at 23:29
2
\$\begingroup\$

I know that my approach not adding a very good value to you, but i would like to share it with you.

Detecting room hours overlapping with this logic is correct, but it is hard to read and understand:-

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;

I think following below approach will make it more readable and understandable from the first sight:-

let [reservedStart, reservedEnd] = reserved, [lectureStart, lectureEnd] = lectureInterval;
let busyHours = [...new Array(reservedEnd - reservedStart)].map((v, i)=> reservedStart+i);
let lectureHours = [...new Array(lectureEnd - lectureStart)].map((v, i)=> lectureStart+i);
roomBusyInLectureHours = busyHours.filter(hour => lectureHours.includes(hour)).length > 0;
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review. Your answer would be improved by explaining exactly what you changed and why it is an improvement. There is no need to reproduce all of the code if you have only changed a small bit; doing so only makes it harder to see what you have done. \$\endgroup\$ – VisualMelon Aug 24 at 18:07
  • \$\begingroup\$ @VisualMelon Thanks for your comment, answer is edited accordingly \$\endgroup\$ – Mohammed Rabea Aug 24 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.