# Activity Selection Algorithm

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.

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.