1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.