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](https://en.wikipedia.org/wiki/Interval_scheduling#Greedy_polynomial_solution), 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](https://en.wikipedia.org/wiki/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?