You are planning a canoe trip through a tidal estuary (a network of waterways subject to tides).You can paddle only by day (sunrise to sunset). A particular difficulty is that many of the places you can consider stopping will only have enough water to float your canoe when the tide is sufficiently high, and getting stuck offshore in the mud for several hours is not your idea of a good time!
You have a list of the available docks, in the order you will encounter them. For each dock you know how many miles it is from your starting point and for how many hours before and after low tide it cannot be reached. You need not stop at each dock, and the main channel of the waterway will always have enough water for you to make progress if you wish to bypass one or more docks.You want to be sure, however, that you put in to an accessible dock by sunset on each day. You also cannot depart from a dock in the morning until enough water is available.
The time of sunrise, sunset, and low tides for each day will change slightly. So successive sunrises will not be exactly 24 hours apart nor sunsets, nor will successive low tides occur exactly 12 hours apart. Over the limited number of days for your trip, we can approximate these changes as a fixed number of minutes per day away from the ideal.
Write a program to prepare itineraries for such trips, indicating at which docks you will stop at end of each day's paddling. Each itinerary should require as few days as possible. Given a choice of itineraries with the same number of days, choose the one in which you make the most progress in the earlier days.