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);
\$\endgroup\$
5
  • \$\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\$ Aug 18, 2019 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, 2019 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\$ Aug 18, 2019 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\$ Aug 18, 2019 at 23:29
  • \$\begingroup\$ I think you can simplify by using a priority queue which will always keep the first available meeting room at the beginning of the queue: from queue import PriorityQueue def num_rooms(intervals): a = sorted(intervals) q = PriorityQueue() q.put(a[0][1]) for m in a[1:]: min_q = q.get() if m[0] < min_q: q.put(min_q) q.put(m[1]) return q.qsize() \$\endgroup\$
    – Andrew L
    Sep 4, 2021 at 21:47

2 Answers 2

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;
\$\endgroup\$
3
  • 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\$ Aug 24, 2019 at 18:07
  • \$\begingroup\$ @VisualMelon Thanks for your comment, answer is edited accordingly \$\endgroup\$ Aug 24, 2019 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, 2020 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.

\$\endgroup\$
0

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