6
\$\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);
| improve this question | |
\$\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 '19 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 '19 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 '19 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 '19 at 23:29
3
\$\begingroup\$

I know that my approach may not add much value, 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 the approach below will make it more readable and understandable:-

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;
| improve this answer | |
\$\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 '19 at 18:07
  • \$\begingroup\$ @VisualMelon Thanks for your comment, answer is edited accordingly \$\endgroup\$ – Mohammed Rabea Aug 24 '19 at 19:38
  • \$\begingroup\$ I disagree that this solution is more readable or understandable plus it performs badly and uses more memory. One good thing is the destruction assignments in the first line (although it should be split into two separate let statements). The construction of the busyHours and lectureHours uses more memory, is difficult to understand and is duplicated code.A (well commented) function would help a lot. Also lectureHours is unnecessary just to use includes, which performs badly compared with just two comparisons (hour => lectureStart <= hour && hour <= lectureEnd). \$\endgroup\$ – RoToRa Jan 8 at 9:54
1
\$\begingroup\$

Shouldn't you check by >= and <= if the time is equal for two intervals? Currently you're not checking for conflicts.

[0,30],[0,30] for example can not be done on the same room.

| improve this answer | |
\$\endgroup\$

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