Consider an event organizer scheduling a set of n meetings, each with a start and a...

Transcribed Image Text:

Consider an event organizer scheduling a set of n meetings, each with a start and a finish time. Suppose that all the start and finish times are distinct. The event venue has plenty of rooms, but renting a room is expensive. Therefore, the event organizer aims to schedule the meetings so that • each meeting takes place at a different room, • no two meetings that take place in the same room conflict with each other, and • the minimum number of rooms are used for the meetings. For instance, the following four meetings (denoted by different colors) are scheduled to use two rooms: The red and green meetings in Room 1, and the yellow and blue meetings in Room 2. Room 2 Room 1 Design a greedy algorithm to find the minimum number of rooms that are needed to schedule all the meetings subject to the constraints above. (a) (10 points) The greedy choice of "choosing the meeting with the earliest finish time" does not lead to an optimal solution. Please give an example with at most 4 meetings to illustrate this. (b) (10 points) Find a different greedy choice that your algorithm will make at each step, and that leads to an optimal solution. Please explain how optimality is guaranteed. (c) (10 points) Write down a pseudocode for your greedy algorithm. (d) (10 points) Analyze the worst-case asymptotic running time of your greedy algorithm. Consider an event organizer scheduling a set of n meetings, each with a start and a finish time. Suppose that all the start and finish times are distinct. The event venue has plenty of rooms, but renting a room is expensive. Therefore, the event organizer aims to schedule the meetings so that • each meeting takes place at a different room, • no two meetings that take place in the same room conflict with each other, and • the minimum number of rooms are used for the meetings. For instance, the following four meetings (denoted by different colors) are scheduled to use two rooms: The red and green meetings in Room 1, and the yellow and blue meetings in Room 2. Room 2 Room 1 Design a greedy algorithm to find the minimum number of rooms that are needed to schedule all the meetings subject to the constraints above. (a) (10 points) The greedy choice of "choosing the meeting with the earliest finish time" does not lead to an optimal solution. Please give an example with at most 4 meetings to illustrate this. (b) (10 points) Find a different greedy choice that your algorithm will make at each step, and that leads to an optimal solution. Please explain how optimality is guaranteed. (c) (10 points) Write down a pseudocode for your greedy algorithm. (d) (10 points) Analyze the worst-case asymptotic running time of your greedy algorithm.

Answer rating: 100% (QA)

a Earliest finish time greedy choice An example of why choosing the meeting with the earliest finish time doesnt always work is as follows Consider 3 meetings Meeting 1Starts at 1000Ends at 1100 Meeti... View the full answer