Maximize number of museums visited in a day

Question

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.

Suppose that no time is needed in order to travel from one museum to another. Tourist cannot, of course, be in two different museums at the same time.

For example, if given:

+-------------+-------+--------+-------------------+
|   Museum    | Opens | Closes | Duration of visit |
+-------------+-------+--------+-------------------+
| Louvre      | 08:00 | 16:00  | 01:00             |
| Hermitage   | 08:00 | 15:00  | 01:00             |
| Uffizi      | 09:00 | 18:00  | 04:40             |
| Rijksmuseum | 10:00 | 21:00  | 02:20             |
| Vatican     | 08:00 | 15:00  | 05:30             |
+-------------+-------+--------+-------------------+

One itinerary maximizing number of museums visited would be:

Vatican 08:00 - 13:30
Hermitage 13:30 - 14:30
Louvre 14:30 - 15:30
Rijksmuseum 15:30 - 17:50
    ---> Total No. of museums visited: 4

Also, this itinerary would also be valid:

Uffizi 09:00 - 13:40
Hermitage 13:40 - 14:40
Louvre 14:40 - 15:40
Rijksmuseum 15:40 - 17:40
    ---> Total No. of museums visited: 4

There is no preference over different itineraries having the same number of museums!

Things I have tried:

Greedy algorithm

For the sake of simplicity, let us consider the following table:

+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Louvre    | 08:00 | 10:00  | 02:00             |
| Hermitage | 08:00 | 11:00  | 01:00             |
| Uffizi    | 08:00 | 11:00  | 03:00             |
+-----------+-------+--------+-------------------+

Based on Interval scheduling, I tried first sorting this list by earliest museum visit finishing times (i.e. by time museum opens + duration of visit sum):

+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 08:00 | 10:00  | 02:00             |
| Uffizi    | 08:00 | 11:00  | 03:00             |
+-----------+-------+--------+-------------------+

and then "greedily selecting" the next visit, which gives only:

Hermitage 08:00 - 09:00

while the optimal itinerary would be:

Louvre 08:00 - 10:00
Hermitage 10:00 - 11:00

I have also tried sorting the list using different combinations of criteria (opening/closing time, shortest/longest time needed to visit, etc.) to no avail, thus concluding that the greedy algorithm approach is probably not suitable.

---

Dynamic programming

Given that we have to "place the maximum number of visits" in "a container of fixed length", i.e. a 24-hour day, it seemed to me that this problem is a variation of the Knapsack problem.

I have tried solving for an optimal itinerary for some $k$ museum visits, where $0\leq k\leq$ no. of museums, but failed to see the correspondence of $k+1$-th solution to $k$-th solution.

[EDIT: Added examples of what might not work] Suppose that we go hour-by-hour from the latest closing time up to the earliest opening time. (Here, the choice of time step as one hour is for the sake of simplicity and would work only if times where given as integer number of hours, as in the following example.) Considering the following table:

+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 09:00 | 11:00  | 02:00             |
+-----------+-------+--------+-------------------+

At 10:00 o'clock, the tourist can visit:

Hermitage 10:00 - 11:00

At 09:00 o'clock:

Hermitage 10:00 - 11:00

At 08:00 o'clock, still the same:

Hermitage 10:00 - 11:00

i.e. Louvre never appeared because Hermitage occupied its 'time slot' even though the tourist could have gone to Hermitage at 08:00, like so:

Hermitage 08:00 - 09:00
Louvre 09:00 - 11:00

---

Is this problem, then, solvable only by backtracking or similarly brute-force approach? If so, how?

Answer 1

The problem is strongly $NP$-complete by reduction from 3-Partition.

Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$.

Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\ldots,m_{n-1}$ for $1$ unit of time each, and the $i^\textrm{th}$ museum is open from time unit $i\times(M+1)-1$ to time unit $i\times(M+1)$. I.e., there are $n$ museums that can only be visited at one very specific time of day, and they partition the day into $n$ slots of length $M$ each.

For each integer in the 3-Partition instance we now create a museum to visit that can be visited any time during the day, and takes a number of time units equal to the original integer.

Clearly a solutions visiting all museums in a single day corresponds to a solution for the $3$-Partition instance and vice-versa.

This implies that it is unlikely that an algorithm significantly better than brute-force exists. One possible approach would be to use Held-Karp style dynamic programming, similar to solving TSP. One would, for all subsets $S$ of museums and any time of day $T$, compute the maximum number of museums from $S$ that can be visited before time $T$ (i.e., the last visit must be completed before time $T$). This can be evaluated recursively by picking one museum to visit last, and then removing that museum from $S$ and decreasing $T$ and solving the resulting subproblem. This results in an algorithm with running time exponential in the number of museums.

Answer 2

I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day.

In particular: at 11:00pm, what plan gives you the greatest number of museums? Your only option is to go home and see zero.

Now, at 10:00pm, what plan gives you the greatest number of museums? There are only two options here: visit the Hermitage for one hour (so your score is 1 + max_score(11:00pm)) or wait for one hour (so your score is 0 + max_score(11:00pm)).

Continue in this manner, with a nice dynamic-programming memoization table to keep the time complexity low, until you hit the start of the day (the earliest opening time). And voilà!

EDIT: If you need finer granularity than an hour, you can make your times more precise: in your first example, for instance, ten-minute increments will work nicely.