Activity Selection Algorithm

algorithmscomputer science

I have an activity selection problem where I am given a number of rides at an amusement park and their start and finish times. My goal is to create a program which maximize the amount of time spent on the rides.

+---------+-------+--------+
|  Ride   | Start | Finish |
+---------+-------+--------+
| Dumbo   |     0 |      2 |
| Minnie  |     0 |      1 |
| Teacups |     2 |      3 |
| Toad    |     1 |      4 |
| Indiana |     1 |      2 |
| Future  |     3 |      5 |
| Splash  |     2 |      4 |
+---------+-------+--------+

(I have this table as a 2D array in python)

Normally with an activity selection I would think to use apply a greedy approach

But this would instead be solving for a maximum number of rides rather than the maximum time spent on rides.

It was hinted to look at the problem as a graph traversal rather than a dynamic programming problem. In that case I believe I should calculate the total ride durations and use these durations as the edges of a graph. Then apply a longest path algorithm to solve for the longest path in the graph. The problem is i'm not sure how I would build my graph from my arrays.

I think it makes sense as dynamic programming problem however as weighted interval scheduling or weighted activity selection. Where the durations of each ride is the ride weight.

Input: Number of Jobs n = 4
   Job Details {Start Time, Finish Time, Profit}
   Job 1:  {1, 2, 50} 
   Job 2:  {3, 5, 20}
   Job 3:  {6, 19, 100}
   Job 4:  {2, 100, 200}
Output: The maximum profit is 250.

I'm not sure which method is correct to pursue or which would be easier to implement.

Best Answer

This could be solved using A*.

Define your graph such as:

Every activity is a node. An activity $A_i$ that goes from $t_i^{start}$ to $t_i^{end}$ has an edge leading to every activity $A_j$ such that $t_i^{end} \le t_j^{start}$, with a cost $t_j^{start} - t_i^{end}$. Start and end nodes are artificial activities of length $0$ at the start and end of the day.

The shortest path through this graph minimizes the wait time between activities, thus maximizing the time spent on the rides.

Related Question