COMP$2013$ Data Structures and Algorithms

Programming Assignment $2$

Deadline: $10$:$00$am$,29\backslash (\{\}^\{\backslash$text $\{$th $\}\}\backslash )$ Nov, $2024$

Instructions

Submit the soft$-$copy of your program to Learn@PolyU

$\backslash (>\backslash )$ You can only submit one program file $($either C$++$ or Java or Python$),$ and the filename must follow the format below.

Section $1$: Problem

You are given a set of conference rooms and a set of activities. Each conference room has a specific space size, measured as an integer in square feet. Similarly, each activity has a minimum required space, also an integer, necessary for it to be held. An activity can be accommodated in a conference room if and only if the room's space size is greater than or equal to the activity's minimum required space.

The constraints are as follows:

$-$ Each conference room can host at most one activity.

$-$ Each activity must be held in exactly one conference room.

$-$ Conference rooms cannot be divided to host multiple activities, and activities cannot be split across multiple rooms.

The objective is to determine the maximum number of activities that can be arranged in the available conference rooms. The problem does not assume any specific relationship between $\backslash ($ n $\backslash )$ and $\backslash ($ m $\backslash )$; either can be larger than the other.

Write a greedy algorithm to solve the problem with the following input and output. Input:

$-$ An integer $\backslash ($ n $\backslash )$ representing the number of activities.

$-$ An integer $\backslash ($ m $\backslash )$ representing the number of conference rooms.

$-$ An array $\backslash ($ A $\backslash )$ of $\backslash ($ n $\backslash )$ integers where each integer represents the minimum required space for each activity.

$-$ An array $\backslash ($ C $\backslash )$ of $\backslash ($ m $\backslash )$ integers where each integer represents the space size of each conference room.

Output:

$-$ An integer representing the maximum number of activities that can be accommodated in the conference rooms.

Note: You cannot use existing libraries to directly call off$-$the$-$shelf heap, queue, sorting, stack algorithms, but you can implement them when needed. Except these algorithms, you can use existing libraries when necessary, in your program.

Examples for the problem Section $2$: Input and Output Format

You should strictly follow the format requirements, and do not hardcode file names in your program or have unnecessary text output. In Programming Assignment $1,$ TAs helped you modify your code to meet the format requirements. But in this assignment, we will not do so and strictly follow the requirements to grade.

The format of test files is illustrated by example "file$1.$txt$"$ below.

Your program should output on the screen a single value.

Here is a sample of the input file and the output of your program.

The format of the input file is as follows:

$\backslash (>\backslash )$ the $\backslash (1^\{\backslash$text $\{$st $\}\}\backslash )$ line shows the number of activities $\backslash ($ n $\backslash ),$

$\backslash (>\backslash )$ the $\backslash (2^\{\backslash$text $\{$nd $\}\}\backslash )$ line shows the number of conference rooms $\backslash ($ m $\backslash ),$

$\backslash (>\backslash )$ the next $\backslash ($ n $\backslash )$ lines show the minimum required spaces of the $\backslash ($ n $\backslash )$ activities,

$\backslash (>\backslash )$ then, the next $\backslash ($ m $\backslash )$ lines show the space sizes of the $\backslash ($ m $\backslash )$ conference rooms.

$\backslash ($ n $\backslash )$ is integer in the range $\backslash ([1,10000000]\backslash ).$

$\backslash ($ m $\backslash )$ is integer in the range $[1,10000000].$

Space size and minimum required space size are integers in range $[1,2000]$

We will run your program by a command line like:

where the argument "input$123.$txt$"$ is an example of the input filename.

Your program should only output the result integer number.

Please follow the output format above and DO NOT print any extra information.

Your program should pass all possible inputs, including those maybe invalid

$-$ You need to create test cases to debug and test your program's correctness.