How to find the minimum number of containers to complete a certain number of jobs?

Question

I have a code to try and minimise the number of containers that are required to complete all the jobs in the list. No container can run two jobs at the same time is the only condition. Currently my code looks like the following;

The bookingList code respresents [StartTime, EndTime] for each job in hours. Job 1 begins in hour 0 and finishes 708 hours later, job 2 starts in hour 0 and finishes 12 hours later etc

bookingList = [[0, 708], [0, 12], [108, 156], [156, 168], [180, 252], [192, 708], [276, 300], [324, 
324], [372, 384], [516, 516], [528, 552], [564, 588], [564, 624], [564, 636], [612, 624], [660, 684], 
[660, 660], [672, 672], [672, 684], [672, 684]]


import heapq
def schedule(tasks):
    heap = []
    def offer(begin, end):
        while heap and heap[0] <= begin:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
        return len(heap)
    
    return ((offer(begin, end), (begin, end)) for begin, end in sorted(tasks))
for room, meeting in schedule(bookingList):
    print('Meeting {} should occur in room {}'.format(meeting, room))

The output from that code looks like the below;

Meeting ('0', '12') should occur in room 1
Meeting ('0', '708') should occur in room 2
Meeting ('108', '156') should occur in room 3
Meeting ('156', '168') should occur in room 2
Meeting ('180', '252') should occur in room 2
Meeting ('192', '708') should occur in room 3
Meeting ('276', '300') should occur in room 3
Meeting ('324', '324') should occur in room 3
Meeting ('372', '384') should occur in room 3
Meeting ('516', '516') should occur in room 3
Meeting ('528', '552') should occur in room 3
Meeting ('564', '588') should occur in room 3
Meeting ('564', '624') should occur in room 4
Meeting ('564', '636') should occur in room 5
Meeting ('612', '624') should occur in room 5
Meeting ('660', '660') should occur in room 3
Meeting ('660', '684') should occur in room 3
Meeting ('672', '672') should occur in room 4
Meeting ('672', '684') should occur in room 4
Meeting ('672', '684') should occur in room 5

The output isn't quite right as the 2nd meeting and the 4th meeting shouldn't be in the same room as the second job will still be in operation while job 4 starts.

Edit: I am pretty certain that it is a simple fix with line 8;

  while heap and heap[0] <= begin

but I can't quite figure out what it should say

Answer 1

There are a couple of problems in your code:

• Your schedule function is returning the length of the heap, so simply the number of rooms needed to hold all the events in that specific moment, not the event room itself
• You are not keeping track of the different event. If an event starts and ends at the same time, in your code it is almost as if it were the same event.
• With the heappop function you're removing the first element if it's finished, but, this way, you are also changing the location where all other events are saved in the heap without any reference to what their room is (and thus changing it).

A working solution for your problem could be:

bookingList = [[0, 708], [0, 12], [108, 156], [156, 168], [180, 252], [192, 708], [276, 300], [324, 
324], [372, 384], [516, 516], [528, 552], [564, 588], [564, 624], [564, 636], [612, 624], [660, 684], 
[660, 660], [672, 672], [672, 684], [672, 684]]

import heapq
def schedule(tasks):
    global event_id
    heap = []
    event_id = 0
    def offer(begin, end):
        global event_id
        event_id += 1
        for index, event in enumerate(heap):
            if event[1] <= begin:
                heap[index] = (event_id, end)
                return [x[0] for x in heap].index(event_id) + 1
        heapq.heappush(heap, (event_id, end))
        return [x[0] for x in heap].index(event_id) + 1
    
    return ((offer(begin, end), (begin, end)) for begin, end in sorted(tasks))
for room, meeting in schedule(bookingList):
    print('Meeting {} should occur in room {}'.format(meeting, room))

In my solution I decided to save an event_id for each event so that I could identify it independently from the start and end times.
Also I'm not going to delete every time all the events ended by the heap, this would make more complex the management of the heap and would probably require a different structure for the recognition of the room number. Instead, every time a new event must be inserted, I check, in order of room number, if an event in one of the rooms is finished and I replace it, otherwise I add a new room.

The output of this solution is:

Meeting (0, 12) should occur in room 1
Meeting (0, 708) should occur in room 2
Meeting (108, 156) should occur in room 1
Meeting (156, 168) should occur in room 1
Meeting (180, 252) should occur in room 1
Meeting (192, 708) should occur in room 3
Meeting (276, 300) should occur in room 1
Meeting (324, 324) should occur in room 1
Meeting (372, 384) should occur in room 1
Meeting (516, 516) should occur in room 1
Meeting (528, 552) should occur in room 1
Meeting (564, 588) should occur in room 1
Meeting (564, 624) should occur in room 4
Meeting (564, 636) should occur in room 5
Meeting (612, 624) should occur in room 1
Meeting (660, 660) should occur in room 1
Meeting (660, 684) should occur in room 1
Meeting (672, 672) should occur in room 4
Meeting (672, 684) should occur in room 4
Meeting (672, 684) should occur in room 5

(seems correct to me).

Another possible solution, using dictionaries, could be:

bookingList = [[0, 708], [0, 12], [108, 156], [156, 168], [180, 252], [192, 708], [276, 300], [324, 
324], [372, 384], [516, 516], [528, 552], [564, 588], [564, 624], [564, 636], [612, 624], [660, 684], 
[660, 660], [672, 672], [672, 684], [672, 684]]

def schedule(tasks):
    rooms = {}
    assigned_rooms = {}
    for event, timing in tasks.items():
        if any(k for k, v in rooms.items() if v <= timing[0]):
            room_number = next(k for k, v in rooms.items() if v <= timing[0])
            assigned_rooms[event] = room_number
            rooms[room_number] = timing[1]
        else:
            assigned_rooms[event] = len(rooms) + 1
            rooms[len(rooms) + 1] = timing[1]
    return assigned_rooms
    

def convert_to_dictionary(event_list):
    event_dict = {}
    for index, event_timing in enumerate(sorted(event_list)):
        event_dict[f"event_{index}"] = event_timing
    return event_dict


event_dict = convert_to_dictionary(bookingList)
final_schedule = schedule(event_dict)
for event, room in final_schedule.items():
    print(f"Meeting {event} should occur in room {room}")

The output will be:

Meeting event_0 should occur in room 1
Meeting event_1 should occur in room 2
Meeting event_2 should occur in room 1
Meeting event_3 should occur in room 1
Meeting event_4 should occur in room 1
Meeting event_5 should occur in room 3
Meeting event_6 should occur in room 1
Meeting event_7 should occur in room 1
Meeting event_8 should occur in room 1
Meeting event_9 should occur in room 1
Meeting event_10 should occur in room 1
Meeting event_11 should occur in room 1
Meeting event_12 should occur in room 4
Meeting event_13 should occur in room 5
Meeting event_14 should occur in room 1
Meeting event_15 should occur in room 1
Meeting event_16 should occur in room 1
Meeting event_17 should occur in room 4
Meeting event_18 should occur in room 4
Meeting event_19 should occur in room 5

In this solution I suppose to start from the same list as before, convert it to a dictionary with event_number: [starting_hour, ending_hour]. Then I decided to save all the rooms and the time until which they are occupied in a new rooms dictionary and a "final" dictionary (assigned_rooms) containing all the confirmed assignments.

Answer 2

I'm not very familiar with heaps, but I don't see any benefit in using heaps rather than a simpler data structure like a dictionary where it's easier to keep track of the occupied rooms.

Since Lorenzo Zane's answer already fix the approach with heaps, I propose a completely different approach using a dictionary, some functions to manage the rooms (all packed in a class) and a single loop.
In the loop I make use of iterators to get the next start and end times when needed.

class Rooms:
    def __init__(self):
        self.rooms = {}

    def assign_room(self, meeting):
        """assing a meeting to a free room and return the room id """
        for room_id, meeting_in_room in self.rooms.copy().items():
            # checking if there are free rooms
            if meeting_in_room is None:
                u_room = room_id   # get id of first room not in use
                break
        else:
            u_room = len(self.rooms)+1  # all room are used, add a new room. length of dict+1 is the new room id

        self.rooms[u_room] = meeting  # set the room in use
        return u_room

    def empty_room(self, current_time):
        """empty the room in use"""
        for room_id, meeting_in_room in self.rooms.copy().items():
            if meeting_in_room is not None and meeting_in_room[1] < current_time:
                self.rooms[room_id] = None
                break


bookingList = [[0, 708], [0, 12], [108, 156], [156, 168], [180, 252], [192, 708], [276, 300], [324, 
324], [372, 384], [516, 516], [528, 552], [564, 588], [564, 624], [564, 636], [612, 624], [660, 684], 
[660, 660], [672, 672], [672, 684], [672, 684]]

ll = sorted(bookingList)

# get together all starts and ends sorted
relevant_times = sorted([t for interval in ll for t in interval])

starts = [meet[0] for meet in ll]  # these are already sorted
ends = sorted(meet[1] for meet in ll)

i_starts = iter(starts)
i_ends = iter(ends)
meetings = iter(ll)

next_start = next(i_starts)
next_end = next(i_ends)
next_meeting = next(meetings)

used_rooms = Rooms()

for time in relevant_times:
    if time > next_start:
        room = used_rooms.assign_room(next_meeting)
        print('Meeting {} should occur in room {}'.format(next_meeting, room))
        try:
            next_start = next(i_starts)
            next_meeting = next(meetings)
        except StopIteration:
            # set a fake next start after the ending of all meeting, needed to not enter again in this block
            # when the last meeting starts and the iteration is not finished yet
            next_start = relevant_times[-1]+1

    if time > next_end:
        used_rooms.empty_room(time)
        try:
            next_end = next(i_ends)
        except StopIteration:
            pass

The output is:

Meeting [0, 12] should occur in room 1
Meeting [0, 708] should occur in room 2
Meeting [108, 156] should occur in room 1
Meeting [156, 168] should occur in room 3
Meeting [180, 252] should occur in room 1
Meeting [192, 708] should occur in room 3
Meeting [276, 300] should occur in room 1
Meeting [324, 324] should occur in room 1
Meeting [372, 384] should occur in room 1
Meeting [516, 516] should occur in room 1
Meeting [528, 552] should occur in room 1
Meeting [564, 588] should occur in room 1
Meeting [564, 624] should occur in room 4
Meeting [564, 636] should occur in room 1
Meeting [612, 624] should occur in room 5
Meeting [660, 660] should occur in room 1
Meeting [660, 684] should occur in room 1
Meeting [672, 672] should occur in room 4
Meeting [672, 684] should occur in room 4
Meeting [672, 684] should occur in room 5

It looks slightly different from Lorenzo's answer because here if a meeting ends at a certain time and the next meeting starts at the same time, the room is considered still in use.