2
\$\begingroup\$

The Challenge 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.

I believe this code has no errors but if you find any, please do let me know. Otherwise, feel free to use this solution if you get stuck

My Solution

def item_2(element):
    return (element[1]) #Returns second element of tuple for sorting 

classes = [(15,50),(51,53),(54,58),(60,70),(61,63),(65,69),(71,83)]
#classes = [(30, 75), (0, 50), (60, 150), (0, 500), (40, 70)]
classes.sort(key=item_2)

print("The following classes will be needed")
while classes:
    item = classes[0]
    index = 0

    end_time = item[1]
    remaining = classes[1:]
    room_bookings = []
    room_bookings.append(item)
    for next_item in remaining:
        if next_item[0] > end_time:
            room_bookings.append(next_item)
            classes.remove(next_item)
            end_time = next_item[1]
    print(room_bookings)
    classes.remove(item)
\$\endgroup\$
  • 2
    \$\begingroup\$ Hello EML, given the wording "feel free to use this solution if you get stuck" I'm unsure if you're asking for Code Review feedback of your code. Am I misunderstanding your post - do you want a code review? \$\endgroup\$ – Peilonrayz May 25 at 21:00
1
\$\begingroup\$

To clearly show which part of your code is the interesting part, you should define a function:

def rooms_required(classes):
    classes = classes[:] # do not modify the argument, make a copy of it
    rooms_bookings = []

    # TODO: insert your code here.

    return len(rooms_bookings)

To describe the function in more details, you should add some documentation about the expected data types:

from typing import List

def rooms_required(classes: List[(int, int)]) -> int:
    ...

This way, you can easily define several test cases:

def test_rooms_required():

    # The example from the challenge.
    assert rooms_required([(30, 75), (0, 50), (65, 150)]) == 2

    assert rooms_required([]) == 0

    # This class needs no time at all, therefore it doesn't need a room.
    assert rooms_required([(0, 0)]) == 0

    # Classes that go backwards in time should either be ignored or raise an exception.
    assert rooms_required([(1200, 1100)]) == 0

    # Ensure that rooms_required does not modify the given list,
    # as that would be surprising.
    classes = [(0, 1), (0, 2), (0, 3), (2, 3)]
    assert rooms_required(classes) == 3
    assert rooms_required(classes) == 3

Read more about pytest to see how to run these automatic tests.


Some more detailed remarks, from top to bottom:

def item_2(element):
    return (element[1]) #Returns second element of tuple for sorting

Since this challenge is about time spans, it's more helpful to the reader of your code if you call this function end, since it returns the end of a time span.

def end(span):
    return span[1]

And since the meaning of [0] in the code is not really obvious, you should also define:

def start(span):
    return span[0]

Then, instead of span[0] and span[1], you can write start(span) and end(span), which clearly tells a story.

classes = [(15,50),(51,53),(54,58),(60,70),(61,63),(65,69),(71,83)]
#classes = [(30, 75), (0, 50), (60, 150), (0, 500), (40, 70)]

As I mentioned above, instead of testing only one scenario at a time, you should define a function that does the interesting work, which then allows you to have automatic tests, and several of them at the same time.

print("The following classes will be needed")

That's wrong. It should be "the following rooms" instead.

while classes:
    item = classes[0]

The word item is a very general term. A better name for this variable is span.

    index = 0

This variable is not used in the rest of the code. You can remove this line.

    room_bookings = []
    room_bookings.append(item)

You can simplify this into room_bookings = [span].

    for next_item in remaining:
        if next_item[0] > end_time:

Instead of the end_time variable (end time of what exactly?), you can write start(next_span) > end(span), which makes the expression look symmetrical and easy to read aloud: if the next span starts later than the current span ends …

When you use this pattern, you can remove the end_time variable, which will make the code a little shorter.

    print(room_bookings)

The function that computes the room bookings should not print anything. Printing things is the job of the main program. That's a general rule.

\$\endgroup\$

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.