Suppose that you are going on vacation and have a set of activities to select fr

Question

Suppose that you are going on vacation and have a set of activities to select from. Each activity occurs at a specific time (e.g., 1 p.m. 2:00 p.m.). If two activities overlap in time, you cannot participate in both of them. Your goal is to maximize the number of activities that you participate For example, suppose tennis occurs from 1:00 p.m. to 2:00 p.m., sailing is from 1 p.m. 3:00 p.m., skydiving is from 2:00 p.m. 4:00 p.m., biking is from 2:30pm — 3:30pm, and soccer is from 3:30 p.m. 5:00 p.m. You can do tennis, biking, and soccer. It is not possible to do more than three activities given this particular set of times.
Design a greedy algorithm to select no overlapping activities so that the number of activities is maximized. Your algorithm should return the actual activities selected, not just the number of activities.
Note: Please design the algorithm not pseudo code!

Explanation / Answer

Let's say we have activities (1pm, 2pm), (1pm, 3pm), (2pm, 4pm), (2:30pm, 3:30pm), (3:30pm, 5pm)

Following are the steps to solve this problem

So, lets dry run the algorithm

result --> (1pm, 2pm)

current --> (1pm, 3pm), since 1pm (current activity start time) >= 2pm (previous activity end time) is false, don't pick it

result --> (1pm, 2pm)

current --> (2:30pm, 3:30pm), since 2:30pm (current activity start time) >= 2pm (previous activity end time) is true, pick it

result --> (1pm, 2pm), (2:30pm, 3:30pm)

current --> (2pm, 4pm), since 2pm (current activity start time) >= 3:30pm (previous activity end time) is false, don't pick it

result --> (1pm, 2pm), (2:30pm, 3:30pm)

current --> (3:30pm, 5pm), since 3:30pm (current activity start time) >= 3:30pm (previous activity end time) is true, pick it

result --> (1pm, 2pm), (2:30pm, 3:30pm), (3:30pm, 5pm)

So, final result is (1pm, 2pm), (2:30pm, 3:30pm), (3:30pm, 5pm)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.