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  邮箱：99515681@qq.com   WX：codinghelp