Assignment 4 P. 1 / 9
The University of Hong Kong
COMP1117B Computer Programming
Assignment 4
Due date: May 5, 2025 23:59
Reminders
You are reminded that the VPL system on HKU Moodle evaluates your program with full
marks under the condition that your program output is the EXACT MATCH of the expected
output. In other words, any additional or missing space character, newline character, etc.,
will be treated as errors and lead to 0 marks. Also, you are suggested to make more test
cases on your own for testing your program.
Question 1 [50%]
Background
In the busy corporate world, efficient meeting room management is crucial for maintaining
productivity and avoiding scheduling conflicts. Imagine you are working for a company
planning a major office renovation of their headquarters. As part of this renovation, they
need to decide how many meeting rooms to build in their new office to accommodate their
busy schedule of meetings and ensure that all planned meetings can be held without
conflicts.
To make an informed decision, they have collected data on the start and end times of all the
meetings scheduled throughout workdays. Your task is to write a program that helps the
company determine the minimum number of meeting rooms required to accommodate all
the meetings to ensure that no two meetings overlap in the same room.
Task
You are given a file with a list of meeting time intervals consisting of start and end times.
Write a program to determine the minimum number of meeting rooms required to host all
the meetings.
Note that the end time is exclusive, meaning a meeting ends at time can be followed by
another meeting starting at the time . Meeting times may overlap, but a single meeting
room cannot be used for more than one meeting at a time.
Input File
• The file contains number of lines.
• Each line represents a meeting and consists of a pair of times in 24-hour format,
where the first time is the start time and the second time is the end time
Program Input
• The filename of the input file. You can assume the input file and your program are
located in the same folder.
Assignment 4 P. 2 / 9
Program Output
• An integer representing the minimum number of meeting rooms required.
Assumptions
• 1 ≤
• 00: 00 ≤ < ≤ 23: 59 for all meetings
Example
The input file (20250206.txt) has the following content.
09:00-10:00
09:30-13:00
11:00-12:00
12:00-12:10
15:00-16:00
When your program runs, the user enters the filename. The program will read the file and
print the result:
20250206.txt
2
Remarks:
• Meeting 2 (09:30-13:00) overlaps with Meeting 1 (09:00-10:00), Meeting 3 (11:00-
12:00) and Meeting 4 (12:00-12:10), so we need at least two rooms.
• Meeting 4 can start after Meeting 3 ends in the same room, so we need only two
rooms in total.
Hints
• Ensure you understand the problem requirements and constraints. There are many
approaches to solving the problem. You are free to choose which approach to use
based on your understanding and preference.
• One way to solve the problem is to check all possible combinations of meetings to
find the minimum number of sets to include all meetings. This involves comparing
each meeting with every other meeting to see if they overlap. While this method is
straightforward in concept, it may lead to messy code.
• Another way to solve the problem is to sort the start and end times separately and
then iterate through them to count the number of meeting rooms needed. This
method can result in simpler code and has better time efficiency.
Assignment 4 P. 3 / 9
Question 2 [50%]
Background (Continued)
After determining the number of meeting rooms required, the company encountered a
problem that required them to change the plan. Due to budget constraints, the company
can only afford to build one meeting room during their renovation. To make the most
efficient use of this single room, they need to schedule as many meetings as possible
without any overlap. Now, your task is to help them find the maximum number of meetings
that can be scheduled in this single room without any overlap.
Task
Reuse the file in Question 1, which contains a list of meeting time intervals consisting of
start and end times. Write another program to calculate the maximum number of meetings
that can be scheduled in a single room without any overlap.
Program Output
• An integer representing the maximum number of meetings that can be scheduled in
a single room without any overlap.
Example 1
Reuse the input file (20250206.txt) in Question 1.
09:00-10:00
09:30-13:00
11:00-12:00
12:00-12:10
15:00-16:00
When your program runs, the user enters the filename. The program will read the file and
print the result:
20250206.txt
4
Remarks:
• The maximum number of meetings that can be scheduled in a single room without
any overlap are Meetings 1 (09:00-10:00), 3 (11:00-12:00), 4 (12:00-12:10) and 5
(15:00-16:00).
Assignment 4 P. 4 / 9
Example 2
Another input file (20250207.txt) has the following content.
12:00-15:00
13:00-16:00
10:00-11:00
16:00-17:00
16:00-17:35
Program input and output:
20250207.txt
3
Remarks:
• The maximum number of meetings that can be scheduled in a single room without
overlap are Meetings [1 (12:00-15:00), 3 (10:00-11:00), 4 (16:00-17:00)] or [1, 3, 5
(16:00-17:35)].
• There may be more than one combination having the same maximum number of
meetings without overlapping, but they will not affect the integer to be printed.
Hints
• The most straightforward approach is to check all possible combinations of meetings
to find the maximum number of non-overlapping meetings. This method is
straightforward, but the code might be messy.
• Another way to solve the problem is to sort the meetings by their end times and
then go through them to select the maximum number of non-overlapping meetings.
This method can result in simpler code and has a better time efficiency.
o Think about using an approach where you always pick the meeting that ends
the earliest and then move to the next meeting that starts after the current
one ends. Track the end time of the last selected meeting to ensure there is
no overlap with the next selected meeting.
o Learning how to sort a list of tuples may help with your implementation.
a = [(5, 2), (1, 6), (3, 4)]
# Sort by second item
a.sort(key=lambda x: x[1])
print(a)
# output: [(5, 2), (3, 4), (1, 6)]
Assignment 4 P. 5 / 9
Implementation Notes
1. You can assume that user inputs and the input file are always valid. That means you
don’t need to consider cases not mentioned in the requirement.
2. Your program must strictly follow the input and output format. Do not print extra
space characters.
3. Do not presume the filename of the input file provided by the user. The input file is
used to import data only. Do not modify the input file in your program.
4. You can use any built-in Python functions. Despite that, you can still complete this
assignment using the techniques covered by lecture notes and tutorial notes.
5. After the submission deadline, we will grade your program with another set of input
files and test cases.
Submission
Submit your programs to Moodle. Late submissions will not be accepted.
• Submit your code as a Python file (.py).
• The input files are included in the evaluation environment. You do not need to
upload them.
Assignment 4 P. 6 / 9
Input File and Test Cases
The following input files and test cases are used during the submission period. After the
submission deadline, another set of input files and test cases will be used for grading.
請加QQ：99515681 郵箱：
[email protected] WX：codinghelp
